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