home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 3 / PDCD_3.iso / internet / tcpipsrc / h / if / IP / c / IPROUTE < prev   
Encoding:
Text File  |  1994-08-20  |  15.8 KB  |  613 lines
  1. /* Lower half of IP, consisting of gateway routines
  2.  * Includes routing and options processing code
  3.  */
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. #include <string.h>
  7. #include "global.h"
  8. #include "mbuf.h"
  9. #include "internet.h"
  10. #include "timer.h"
  11. #include "netuser.h"
  12. #include "ip.h"
  13. #include "icmp.h"
  14. #include "iface.h"
  15. #include "trace.h"
  16. #include "misc.h"
  17.  
  18. static int16  hash_ip(int32);
  19. static struct route *rt_lookup(int32);
  20.  
  21. struct route *routes[32][NROUTE];       /* Routing table */
  22. struct route r_default;                 /* Default route entry */
  23.  
  24. int32 ip_addr;
  25. struct ip_stats ip_stats;
  26. struct mbuf *loopq;     /* Queue for loopback packets */
  27.  
  28. /* Route an IP datagram. This is the "hopper" through which all IP datagrams,
  29.  * coming or going, must pass.
  30.  *
  31.  * "rxbroadcast" is set to indicate that the packet came in on a subnet
  32.  * broadcast. The router will kick the packet upstairs regardless of the
  33.  * IP destination address.
  34.  */
  35. int ip_route(struct mbuf *bp, char rxbroadcast)
  36. {
  37.   struct ip ip;                   /* IP header being processed */
  38.   int16 ip_len;                   /* IP header length */
  39.   int16 length;                   /* Length of data portion */
  40.   int32 gateway;                  /* Gateway IP address */
  41.   register struct route *rp;      /* Route table entry */
  42.   struct interface *iface;        /* Output interface, possibly forwarded */
  43.   int16 offset;                   /* Offset into current fragment */
  44.   int16 mf_flag;                  /* Original datagram MF flag */
  45.   int strict = 0;                 /* Strict source routing flag */
  46.   char precedence;                /* Extracted from tos field */
  47.   char delay;
  48.   char throughput;
  49.   char reliability;
  50.   int16 opt_len;          /* Length of current option */
  51.   char *opt;              /* -> beginning of current option */
  52.   char *ptr;              /* -> pointer field in source route fields */
  53.   struct mbuf *tbp;
  54.  
  55.   ip_stats.total++;
  56.   if (len_mbuf(bp) < IPLEN)
  57.   {
  58.     /* The packet is shorter than a legal IP header */
  59.     ip_stats.runt++;
  60.     free_p(bp);
  61.     return -1;
  62.   }
  63.   /* Sneak a peek at the IP header's IHL field to find its length */
  64.   ip_len = (bp->data[0] & 0xf) << 2;
  65.   if(ip_len < IPLEN)
  66.   {
  67.     /* The IP header length field is too small */
  68.     ip_stats.length++;
  69.     free_p(bp);
  70.     return -1;
  71.   }
  72.   if(cksum(NULLHEADER,bp,ip_len) != 0)
  73.   {
  74.     /* Bad IP header checksum; discard */
  75.     ip_stats.checksum++;
  76.     free_p(bp);
  77.     return -1;
  78.   }
  79.   /* Extract IP header */
  80.   ntohip(&ip,&bp);
  81.  
  82.   if(ip.version != IPVERSION)
  83.   {
  84.     /* We can't handle this version of IP */
  85.     ip_stats.version++;
  86.     free_p(bp);
  87.     return -1;
  88.   }
  89.   /* Trim data segment if necessary. */
  90.   length = ip.length - ip_len;    /* Length of data portion */
  91.   trim_mbuf(&bp,length);  
  92.  
  93.   /* Process options, if any. Also compute length of secondary IP
  94.            * header in case fragmentation is needed later
  95.            */
  96.   strict = 0;
  97.   for(opt = ip.options; opt < &ip.options[ip.optlen];opt += opt_len)
  98.   {
  99.  
  100.     /* Most options have a length field. If this is a EOL or NOOP,
  101.                      * this (garbage) value won't be used
  102.                      */
  103.     opt_len = uchar(opt[1]);
  104.  
  105.     switch(opt[0] & OPT_NUMBER)
  106.     {
  107.     case IP_EOL:
  108.       goto no_opt;    /* End of options list, we're done */
  109.     case IP_NOOP:
  110.       opt_len = 1;
  111.       break;          /* No operation, skip to next option */
  112.     case IP_SSROUTE:        /* Strict source route & record route */
  113.       strict = 1;     /* note fall-thru */
  114.     case IP_LSROUTE:        /* Loose source route & record route */
  115.       /* Source routes are ignored unless we're in the
  116.                                * destination field
  117.                                */
  118.       if(ip.dest != ip_addr)
  119.         break;  /* Skip to next option */
  120.       if(uchar(opt[2]) >= opt_len)
  121.       {
  122.         break;  /* Route exhausted; it's for us */
  123.       }
  124.       /* Put address for next hop into destination field,
  125.                                * put our address into the route field, and bump
  126.                                * the pointer
  127.                                */
  128.       ptr = opt + uchar(opt[2]) - 1;
  129.       ip.dest = get32(ptr);
  130.       put32(ptr,ip_addr);
  131.       opt[2] += 4;
  132.       break;
  133.     case IP_RROUTE: /* Record route */
  134.       if(uchar(opt[2]) >= opt_len)
  135.       {
  136.         /* Route area exhausted; kick back an error */
  137.         union icmp_args icmp_args;
  138.  
  139.         icmp_args.pointer = IPLEN + opt - ip.options;
  140.         icmp_output(&ip,bp,PARAM_PROB,0,&icmp_args);
  141.         free_p(bp);
  142.         return -1;
  143.       }
  144.       /* Add our address to the route */
  145.       ptr = opt + uchar(opt[2]) - 1;
  146.       ptr = put32(ptr,ip_addr);
  147.       opt[2] += 4;
  148.       break;
  149.     }
  150.   }
  151. no_opt:
  152.  
  153.   /* See if it's a broadcast or addressed to us, and kick it upstairs */
  154.   if(ip.dest == ip_addr || rxbroadcast)
  155.   {
  156.     /* If this is a local loopback packet, place on the loopback
  157.                      * queue for processing in the main loop. This prevents the
  158.                      * infinite stack recursion and other problems that would
  159.                      * otherwise occur when we talk to ourselves, e.g., with ftp
  160.                      */
  161.     if(ip.source == ip_addr)
  162.     {
  163.       /* Put IP header back on */
  164.       if((tbp = htonip(&ip,bp)) == NULLBUF)
  165.       {
  166.         free_p(bp);
  167.         return -1;
  168.       }
  169.       /* Copy loopback packet into new buffer.
  170.                                * This avoids an obscure problem with TCP which
  171.                                * dups its outgoing data before transmission and
  172.                                * then frees it when an ack comes, even though the
  173.                                * receiver might not have actually read it yet
  174.                                */
  175.       bp = copy_p(tbp,len_mbuf(tbp));
  176.       free_p(tbp);
  177.       if(bp == NULLBUF)
  178.         return -1;
  179.       enqueue(&loopq,bp);
  180.     } 
  181.     else {
  182.       ip_recv(&ip,bp,rxbroadcast);
  183.     }
  184.     return 0;
  185.   }
  186.  
  187.   /* Decrement TTL and discard if zero */
  188.   if(--ip.ttl == 0)
  189.   {
  190.     /* Send ICMP "Time Exceeded" message */
  191.     icmp_output(&ip,bp,TIME_EXCEED,0,NULLICMP);
  192.     free_p(bp);
  193.     return -1;
  194.   }
  195.   /* Look up target address in routing table */
  196.   if((rp = rt_lookup(ip.dest)) == NULLROUTE)
  197.   {
  198.     /* No route exists, return unreachable message */
  199.     icmp_output(&ip,bp,DEST_UNREACH,HOST_UNREACH,NULLICMP);
  200.     free_p(bp);
  201.     return -1;
  202.   }
  203.   /* Check for output forwarding and divert if necessary */
  204.   iface = rp->interface;
  205.   if(iface->forw != NULLIF)
  206.     iface = iface->forw;
  207.  
  208.   /* Find gateway; zero gateway in routing table means "send direct" */
  209.   if(rp->gateway == (int32)0)
  210.     gateway = ip.dest;
  211.   else
  212.       gateway = rp->gateway;
  213.  
  214.   if(strict && gateway != ip.dest)
  215.   {
  216.     /* Strict source routing requires a direct entry */
  217.     icmp_output(&ip,bp,DEST_UNREACH,ROUTE_FAIL,NULLICMP);
  218.     free_p(bp);
  219.     return -1;
  220.   }
  221.   precedence = PREC(ip.tos);
  222.   delay = ip.tos & DELAY;
  223.   throughput = ip.tos & THRUPUT;
  224.   reliability = ip.tos & RELIABILITY;
  225.  
  226.   if(ip.length <= iface->mtu)
  227.   {
  228.     /* Datagram smaller than interface MTU; put header
  229.                      * back on and send normally
  230.                      */
  231.     if((tbp = htonip(&ip,bp)) == NULLBUF)
  232.     {
  233.       free_p(bp);
  234.       return -1;
  235.     }
  236.     return (*iface->send)(tbp,iface,gateway,
  237.     precedence,delay,throughput,reliability);
  238.   }
  239.   /* Fragmentation needed */
  240.   if(ip.fl_offs & DF)
  241.   {
  242.     /* Don't Fragment set; return ICMP message and drop */
  243.     icmp_output(&ip,bp,DEST_UNREACH,FRAG_NEEDED,NULLICMP);
  244.     free_p(bp);
  245.     return -1;
  246.   }
  247.   /* Create fragments */
  248.   offset = (ip.fl_offs & F_OFFSET) << 3;
  249.   mf_flag = ip.fl_offs & MF;      /* Save original MF flag */
  250.   while(length != 0)
  251.   {             /* As long as there's data left */
  252.     int16 fragsize;         /* Size of this fragment's data */
  253.     struct mbuf *f_data;    /* Data portion of fragment */
  254.  
  255.     /* After the first fragment, should remove those
  256.                      * options that aren't supposed to be copied on fragmentation
  257.                      */
  258.     ip.fl_offs = offset >> 3;
  259.     if(length + ip_len <= iface->mtu)
  260.     {
  261.       /* Last fragment; send all that remains */
  262.       fragsize = length;
  263.       ip.fl_offs |= mf_flag;  /* Pass original MF flag */
  264.     } 
  265.     else {
  266.       /* More to come, so send multiple of 8 bytes */
  267.       fragsize = (iface->mtu - ip_len) & 0xfff8;
  268.       ip.fl_offs |= MF;
  269.     }
  270.     ip.length = fragsize + ip_len;
  271.  
  272.     /* Move the data fragment into a new, separate mbuf */
  273.     if((f_data = alloc_mbuf(fragsize)) == NULLBUF)
  274.     {
  275.       free_p(bp);
  276.       return -1;
  277.     }
  278.     f_data->cnt = pullup(&bp,f_data->data,fragsize);
  279.  
  280.     /* Put IP header back on */
  281.     if((tbp = htonip(&ip,f_data)) == NULLBUF)
  282.     {
  283.       free_p(f_data);
  284.       free_p(bp);
  285.       return -1;
  286.     }
  287.     /* and ship it out */
  288.     if((*iface->send)(tbp,iface,gateway,
  289.     precedence,delay,throughput,reliability) == -1)
  290.       return -1;
  291.  
  292.     offset += fragsize;
  293.     length -= fragsize;
  294.   }
  295.   return 0;
  296. }
  297.  
  298. struct rt_cache rt_cache;
  299.  
  300. /* Add an entry to the IP routing table. Returns 0 on success, -1 on failure */
  301. int rt_add(int32 target, unsigned int bits, int32 gateway,
  302. int metric, struct interface *interface)
  303. {
  304.   struct route *rp,**hp;
  305.   int16 i;
  306.   int32 mask;
  307.  
  308.   if(interface == NULLIF)
  309.     return -1;
  310.  
  311.   rt_cache.target = 0;    /* Flush cache */
  312.  
  313.   /* Zero bits refers to the default route */
  314.   if(bits == 0)
  315.   {
  316.     rp = &r_default;
  317.   } 
  318.   else
  319.   {
  320.     if(bits > 32)
  321.       bits = 32;
  322.  
  323.     /* Mask off don't-care bits */
  324.     mask = 0xffffffff;
  325.     for(i=31;i >= bits;i--)
  326.       mask <<= 1;
  327.  
  328.     target &= mask;
  329.     /* Search appropriate chain for existing entry */
  330.     for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next)
  331.     {
  332.       if(rp->target == target)
  333.         break;
  334.     }
  335.   }
  336.   if(rp == NULLROUTE)
  337.   {
  338.     /* The target is not already in the table, so create a new
  339.                      * entry and put it in.
  340.                      */
  341.     if((rp = (struct route *)malloc(sizeof(struct route))) == NULLROUTE)
  342.       return -1;      /* No space */
  343.     /* Insert at head of table */
  344.     rp->prev = NULLROUTE;
  345.     hp = &routes[bits-1][hash_ip(target)];
  346.     rp->next = *hp;
  347.     if(rp->next != NULLROUTE)
  348.       rp->next->prev = rp;
  349.     *hp = rp;
  350.   }
  351.   rp->target = target;
  352.   rp->gateway = gateway;
  353.   rp->metric = metric;
  354.   rp->interface = interface;
  355.  
  356.   return 0;
  357. }
  358.  
  359. /* Remove an entry from the IP routing table. Returns 0 on success, -1
  360.  * if entry was not in table.
  361.  */
  362. int rt_drop(int32 target, unsigned int bits)
  363. {
  364.   register struct route *rp;
  365.   unsigned int i;
  366.   int32 mask;
  367.  
  368.   rt_cache.target = 0;    /* Flush the cache */
  369.  
  370.   if(bits == 0)
  371.   {
  372.     /* Nail the default entry */
  373.     r_default.interface = NULLIF;
  374.     return 0;
  375.   }
  376.   if(bits > 32)
  377.     bits = 32;
  378.  
  379.   /* Mask off don't-care bits */
  380.   mask = 0xffffffff;
  381.   for(i=31;i >= bits;i--)
  382.     mask <<= 1;
  383.  
  384.   target &= mask;
  385.  
  386.   /* Search appropriate chain for existing entry */
  387.   for(rp = routes[bits-1][hash_ip(target)];rp != NULLROUTE;rp = rp->next)
  388.   {
  389.     if(rp->target == target)
  390.       break;
  391.   }
  392.   if(rp == NULLROUTE)
  393.     return -1;      /* Not in table */
  394.  
  395.   if(rp->next != NULLROUTE)
  396.     rp->next->prev = rp->prev;
  397.   if(rp->prev != NULLROUTE)
  398.     rp->prev->next = rp->next;
  399.   else
  400.       routes[bits-1][hash_ip(target)] = rp->next;
  401.  
  402.   free((char *)rp);
  403.   return 0;
  404. }
  405.  
  406. /* Compute hash function on IP address */
  407. static int16 hash_ip(register int32 addr)
  408. {
  409.   register int16 ret;
  410.  
  411.   ret = hiword(addr);
  412.   ret ^= loword(addr);
  413.   ret %= NROUTE;
  414.   return ret;
  415. }
  416. /* Given an IP address, return the MTU of the local interface used to
  417.  * reach that destination. This is used by TCP to avoid local fragmentation
  418.  */
  419. int16 ip_mtu(int32 addr)
  420. {
  421.   register struct route *rp;
  422.   struct interface *iface;
  423.  
  424.   rp = rt_lookup(addr);
  425.   if(rp == NULLROUTE || rp->interface == NULLIF)
  426.     return 0;
  427.  
  428.   iface = rp->interface;
  429.   if(iface->forw != NULLIF)
  430.     return iface->forw->mtu;
  431.   else
  432.       return iface->mtu;
  433. }
  434. /* Look up target in hash table, matching the entry having the largest number
  435.  * of leading bits in common. Return default route if not found;
  436.  * if default route not set, return NULLROUTE
  437.  */
  438. static struct route *rt_lookup(int32 target)
  439. {
  440.   register struct route *rp;
  441.   int bits;
  442.   int32 tsave;
  443.   int32 mask;
  444.  
  445.   if(target == rt_cache.target)
  446.     return rt_cache.route;
  447.  
  448.   tsave = target;
  449.  
  450.   mask = ~0;      /* All ones */
  451.   for(bits = 31;bits >= 0; bits--)
  452.   {
  453.     target &= mask;
  454.     for(rp = routes[bits][hash_ip(target)];rp != NULLROUTE;rp = rp->next)
  455.     {
  456.       if(rp->target == target)
  457.       {
  458.         /* Stash in cache and return */
  459.         rt_cache.target = tsave;
  460.         rt_cache.route = rp;
  461.         return rp;
  462.       }
  463.     }
  464.     mask <<= 1;
  465.   }
  466.   if(r_default.interface != NULLIF)
  467.   {
  468.     rt_cache.target = tsave;
  469.     rt_cache.route = &r_default;
  470.     return &r_default;
  471.   } 
  472.   else
  473.       return NULLROUTE;
  474. }
  475. /* Convert IP header in host format to network mbuf */
  476. struct mbuf *htonip(struct ip *ip, struct mbuf *data)
  477. {
  478.   int16 hdr_len;
  479.   struct mbuf *bp;
  480.   register char *cp;
  481.   int16 checksum;
  482.  
  483.   hdr_len = IPLEN + ip->optlen;
  484.   if((bp = pushdown(data,hdr_len)) == NULLBUF)
  485.   {
  486.     free_p(data);
  487.     return NULLBUF;
  488.   }
  489.   cp = bp->data;
  490.  
  491.   *cp++ = (IPVERSION << 4) | (hdr_len >> 2);
  492.   *cp++ = ip->tos;
  493.   cp = put16(cp,ip->length);
  494.   cp = put16(cp,ip->id);
  495.   cp = put16(cp,ip->fl_offs);
  496.   *cp++ = ip->ttl;
  497.   *cp++ = ip->protocol;
  498.   cp = put16(cp,0);       /* Clear checksum */
  499.   cp = put32(cp,ip->source);
  500.   cp = put32(cp,ip->dest);
  501.   if(ip->optlen != 0)
  502.     memcpy(cp,ip->options,ip->optlen);
  503.  
  504.   /* Compute checksum and insert into header */
  505.   checksum = cksum(NULLHEADER,bp,hdr_len);
  506.   put16(&bp->data[10],checksum);
  507.  
  508.   return bp;
  509. }
  510. /* Extract an IP header from mbuf */
  511. int ntohip(struct ip *ip, struct mbuf **bpp)
  512. {
  513.   char v_ihl;
  514.   int16 ihl;
  515.  
  516.   v_ihl = pullchar(bpp);
  517.   ip->version = (v_ihl >> 4) & 0xf;
  518.   ip->tos = pullchar(bpp);
  519.   ip->length = pull16(bpp);
  520.   ip->id = pull16(bpp);
  521.   ip->fl_offs = pull16(bpp);
  522.   ip->ttl = pullchar(bpp);
  523.   ip->protocol = pullchar(bpp);
  524.   (void)pull16(bpp);      /* Toss checksum */
  525.   ip->source = pull32(bpp);
  526.   ip->dest = pull32(bpp);
  527.  
  528.   ihl = (v_ihl & 0xf) << 2;
  529.   if(ihl < IPLEN)
  530.   {
  531.     /* Bogus packet; header is too short */
  532.     return -1;
  533.   }
  534.   ip->optlen = ihl - IPLEN;
  535.   if(ip->optlen != 0)
  536.     pullup(bpp,ip->options,ip->optlen);
  537.  
  538.   return ip->optlen + IPLEN;
  539. }
  540. /* Perform end-around-carry adjustment */
  541. int16 eac(register int32 sum)
  542. {
  543.   register int16 csum;
  544.  
  545.   while((csum = sum >> 16) != 0)
  546.     sum = csum + (sum & 0xffffL);
  547.   return (int16) (sum & 0xffffl); /* Chops to 16 bits */
  548. }
  549. /* Checksum a mbuf chain, with optional pseudo-header */
  550. int16 cksum(struct pseudo_header *ph, struct mbuf *m, int16 len)
  551. {
  552.   register unsigned int cnt, total;
  553.   register int32 sum, csum;
  554.   register char *up;
  555.   int16 csum1;
  556.   int swap = 0;
  557.  
  558.   sum = 0l;
  559.  
  560.   /* Sum pseudo-header, if present */
  561.   if(ph != NULLHEADER)
  562.   {
  563.     sum = hiword(ph->source);
  564.     sum += loword(ph->source);
  565.     sum += hiword(ph->dest);
  566.     sum += loword(ph->dest);
  567.     sum += uchar(ph->protocol);
  568.     sum += ph->length;
  569.   }
  570.   /* Now do each mbuf on the chain */
  571.   for(total = 0; m != NULLBUF && total < len; m = m->next) {
  572.     cnt = min(m->cnt, len - total);
  573.     up = (char *)m->data;
  574.     csum = 0;
  575.  
  576.     if(((long)up) & 1)
  577.     {
  578.       /* Handle odd leading byte */
  579.       if(swap)
  580.         csum = uchar(*up++);
  581.       else
  582.         csum = (int16)(uchar(*up++) << 8);
  583.       cnt--;
  584.       swap = !swap;
  585.     }
  586.     if(cnt > 1)
  587.     {
  588.       /* Have the primitive checksumming routine do most of
  589.                                * the work. At this point, up is guaranteed to be on
  590.                                * a short boundary
  591.                                */
  592.       csum1 = lcsum((int16 *)up, cnt >> 1);
  593.       if(swap)
  594.         csum1 = (csum1 << 8) | (csum1 >> 8);
  595.       csum += csum1;
  596.     }
  597.     /* Handle odd trailing byte */
  598.     if(cnt & 1)
  599.     {
  600.       if(swap)
  601.         csum += uchar(up[--cnt]);
  602.       else
  603.         csum += (int16)(uchar(up[--cnt]) << 8);
  604.       swap = !swap;
  605.     }
  606.     sum += csum;
  607.     total += m->cnt;
  608.   }
  609.   /* Do final end-around carry, complement and return */
  610.   return ~eac(sum) & 0xffff;
  611. }
  612.  
  613.