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