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