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