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