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