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