home *** CD-ROM | disk | FTP | other *** search
/ Media Share 9 / MEDIASHARE_09.ISO / hamradio / s920603.zip / IPROUTE.C < prev    next >
C/C++ Source or Header  |  1992-06-02  |  20KB  |  766 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() != 0)
  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,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.      * The outer source address is taken from the encap interface
  459.      * structure. This defaults to INADDR_ANY, so unless it is
  460.      * changed (with iface encap ipaddr ...), the IP address
  461.      * of the physical interface used to reach the encap gateway
  462.      * will be used.
  463.      */
  464.     return ip_send(Encap.addr,gateway,IP_PTCL,0,0,bp,0,0,0);
  465. }
  466. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  467. struct route *
  468. rt_add(target,bits,gateway,iface,metric,ttl,private)
  469. int32 target;        /* Target IP address prefix */
  470. unsigned int bits;    /* Size of target address prefix in bits (0-32) */
  471. int32 gateway;        /* Optional gateway to be reached via interface */
  472. struct iface *iface;    /* Interface to which packet is to be routed */
  473. int32 metric;        /* Metric for this route entry */
  474. int32 ttl;        /* Lifetime of this route entry in sec */
  475. char private;        /* Inhibit advertising this entry ? */
  476. {
  477.     struct route *rp,**hp;
  478.     struct route *rptmp;
  479.     int32 gwtmp;
  480.  
  481.     if(iface == NULLIF)
  482.         return NULLROUTE;
  483.  
  484.     if(bits > 32)
  485.         bits = 32;        /* Bulletproofing */
  486.  
  487.     if(bits == 32 && ismyaddr(target))
  488.         return NULLROUTE;    /* Don't accept routes to ourselves */
  489.  
  490.     /* Mask off don't-care bits of target */
  491.     target &= ~0L << (32-bits);
  492.  
  493.     /* Encapsulated routes must specify gateway, and it can't be
  494.      *  ourselves
  495.      */
  496.     if(iface == &Encap && (gateway == 0 || ismyaddr(gateway)))
  497.         return NULLROUTE;
  498.  
  499.     Rt_cache.route = NULLROUTE;    /* Flush cache */
  500.  
  501.     /* Zero bits refers to the default route */
  502.     if(bits == 0){
  503.         rp = &R_default;
  504.     } else {
  505.         rp = rt_blookup(target,bits);
  506.     }
  507.     if(rp == NULLROUTE){
  508.         /* The target is not already in the table, so create a new
  509.          * entry and put it in.
  510.          */
  511.         rp = (struct route *)callocw(1,sizeof(struct route));
  512.         /* Insert at head of table */
  513.         rp->prev = NULLROUTE;
  514.         hp = &Routes[bits-1][hash_ip(target)];
  515.         rp->next = *hp;
  516.         if(rp->next != NULLROUTE)
  517.             rp->next->prev = rp;
  518.         *hp = rp;
  519.         rp->uses = 0;
  520.     }
  521.     rp->target = target;
  522.     rp->bits = bits;
  523.     rp->gateway = gateway;
  524.     rp->metric = metric;
  525.     rp->iface = iface;
  526.     rp->flags = private ? RTPRIVATE : 0;    /* Should anyone be told of this route? */
  527.     rp->timer.func = rt_timeout;  /* Set the timer field */
  528.     rp->timer.arg = (void *)rp;
  529.     set_timer(&rp->timer,ttl*1000L);
  530.     stop_timer(&rp->timer);
  531.     start_timer(&rp->timer); /* start the timer if appropriate */
  532.  
  533.     /* Check to see if this created an encapsulation loop */
  534.     gwtmp = gateway;
  535.     for(;;){
  536.         rptmp = rt_lookup(gwtmp);
  537.         if(rptmp == NULLROUTE)
  538.             break;    /* No route to gateway, so no loop */
  539.         if(rptmp->iface != &Encap)
  540.             break;    /* Non-encap interface, so no loop */
  541.         if(rptmp == rp){
  542.             rt_drop(target,bits);    /* Definite loop */
  543.             return NULLROUTE;
  544.         }
  545.         if(rptmp->gateway != 0)
  546.             gwtmp = rptmp->gateway;
  547.     }
  548.     return rp;
  549. }
  550.  
  551. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  552.  * if entry was not in table.
  553.  */
  554. int
  555. rt_drop(target,bits)
  556. int32 target;
  557. unsigned int bits;
  558. {
  559.     register struct route *rp;
  560.  
  561.     Rt_cache.route = NULLROUTE;    /* Flush the cache */
  562.  
  563.     if(bits == 0){
  564.         /* Nail the default entry */
  565.         stop_timer(&R_default.timer);
  566.         R_default.iface = NULLIF;
  567.         return 0;
  568.     }
  569.     if(bits > 32)
  570.         bits = 32;
  571.  
  572.     /* Mask off target according to width */
  573.     target &= ~0L << (32-bits);
  574.  
  575.     /* Search appropriate chain for existing entry */
  576.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  577.         if(rp->target == target)
  578.             break;
  579.     }
  580.     if(rp == NULLROUTE)
  581.         return -1;    /* Not in table */
  582.  
  583.     stop_timer(&rp->timer);
  584.     if(rp->next != NULLROUTE)
  585.         rp->next->prev = rp->prev;
  586.     if(rp->prev != NULLROUTE)
  587.         rp->prev->next = rp->next;
  588.     else
  589.         Routes[bits-1][hash_ip(target)] = rp->next;
  590.  
  591.     free((char *)rp);
  592.     return 0;
  593. }
  594. #ifdef    notdef
  595.  
  596. /* Compute hash function on IP address */
  597. static int16
  598. hash_ip(addr)
  599. register int32 addr;
  600. {
  601.     register int16 ret;
  602.  
  603.     ret = hiword(addr);
  604.     ret ^= loword(addr);
  605.     return (int16)(ret % HASHMOD);
  606. }
  607. #endif
  608. #ifndef    GWONLY
  609. /* Given an IP address, return the MTU of the local interface used to
  610.  * reach that destination. This is used by TCP to avoid local fragmentation
  611.  */
  612. int16
  613. ip_mtu(addr)
  614. int32 addr;
  615. {
  616.     register struct route *rp;
  617.     struct iface *iface;
  618.  
  619.     rp = rt_lookup(addr);
  620.     if(rp == NULLROUTE || rp->iface == NULLIF)
  621.         return 0;
  622.  
  623.     iface = rp->iface;
  624.     if(iface->forw != NULLIF)
  625.         return iface->forw->mtu;
  626.     else
  627.         return iface->mtu;
  628. }
  629. /* Given a destination address, return the IP address of the local
  630.  * interface that will be used to reach it. If there is no route
  631.  * to the destination, pick the first non-loopback address.
  632.  */
  633. int32
  634. locaddr(addr)
  635. int32 addr;
  636. {
  637.     register struct route *rp;
  638.     struct iface *ifp;
  639.  
  640.     if(ismyaddr(addr) != NULLIF)
  641.         return addr;    /* Loopback case */
  642.  
  643.     rp = rt_lookup(addr);
  644.     if(rp != NULLROUTE && rp->iface != NULLIF)
  645.         ifp = rp->iface;
  646.     else {
  647.         /* No route currently exists, so just pick the first real
  648.          * interface and use its address
  649.          */
  650.         for(ifp = Ifaces;ifp != NULLIF;ifp = ifp->next){
  651.             if(ifp != &Loopback && ifp != &Encap)
  652.                 break;
  653.         }
  654.     }
  655.     if(ifp == NULLIF || ifp == &Loopback)
  656.         return 0;    /* No dice */
  657.  
  658.     if(ifp == &Encap){
  659.         /* Recursive call - we assume that there are no circular
  660.          * encapsulation references in the routing table!!
  661.          * (There is a check at the end of rt_add() that goes to
  662.          * great pains to ensure this.)
  663.          */
  664.         return locaddr(rp->gateway);
  665.     }
  666.     if(ifp->forw != NULLIF)
  667.         return ifp->forw->addr;
  668.     else
  669.         return ifp->addr;
  670. }
  671. #endif
  672. /* Look up target in hash table, matching the entry having the largest number
  673.  * of leading bits in common. Return default route if not found;
  674.  * if default route not set, return NULLROUTE
  675.  */
  676. struct route *
  677. rt_lookup(target)
  678. int32 target;
  679. {
  680.     register struct route *rp;
  681.     int bits;
  682.     int32 tsave;
  683.     int32 mask;
  684.  
  685.     /* Examine cache first */
  686.     if(target == Rt_cache.target && Rt_cache.route != NULLROUTE)
  687.         return Rt_cache.route;
  688.  
  689.     tsave = target;
  690.  
  691.     mask = ~0;    /* All ones */
  692.     for(bits = 31;bits >= 0; bits--){
  693.         target &= mask;
  694.         for(rp = Routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  695.             if(rp->target == target){
  696.                 /* Stash in cache and return */
  697.                 Rt_cache.target = tsave;
  698.                 Rt_cache.route = rp;
  699.                 return rp;
  700.             }
  701.         }
  702.         mask <<= 1;
  703.     }
  704.     if(R_default.iface != NULLIF){
  705.         Rt_cache.target = tsave;
  706.         Rt_cache.route = &R_default;
  707.         return &R_default;
  708.     } else
  709.         return NULLROUTE;
  710. }
  711. /* Search routing table for entry with specific width */
  712. struct route *
  713. rt_blookup(target,bits)
  714. int32 target;
  715. unsigned int bits;
  716. {
  717.     register struct route *rp;
  718.  
  719.     if(bits == 0){
  720.         if(R_default.iface != NULLIF)
  721.             return &R_default;
  722.         else
  723.             return NULLROUTE;
  724.     }
  725.     /* Mask off target according to width */
  726.     target &= ~0L << (32-bits);
  727.  
  728.     for(rp = Routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next){
  729.         if(rp->target == target){
  730.             return rp;
  731.         }
  732.     }
  733.     return NULLROUTE;
  734. }
  735. /* Scan the routing table. For each entry, see if there's a less-specific
  736.  * one that points to the same interface and gateway. If so, delete
  737.  * the more specific entry, since it is redundant.
  738.  */
  739. void
  740. rt_merge(trace)
  741. int trace;
  742. {
  743.     int bits,i,j;
  744.     struct route *rp,*rpnext,*rp1;
  745.  
  746.     for(bits=32;bits>0;bits--){
  747.         for(i = 0;i<HASHMOD;i++){
  748.             for(rp = Routes[bits-1][i];rp != NULLROUTE;rp = rpnext){
  749.                 rpnext = rp->next;
  750.                 for(j=bits-1;j >= 0;j--){
  751.                     if((rp1 = rt_blookup(rp->target,j)) != NULLROUTE
  752.                      && rp1->iface == rp->iface
  753.                      && rp1->gateway == rp->gateway){
  754.                         if(trace > 1)
  755.                             printf("merge %s %d\n",
  756.                              inet_ntoa(rp->target),
  757.                              rp->bits);
  758.                         rt_drop(rp->target,rp->bits);
  759.                         break;
  760.                     }
  761.                 }
  762.             }
  763.         }
  764.     }
  765. }
  766.