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