768 lines · c
1/*2 * Routines to compress and uncompress tcp packets (for transmission3 * over low speed serial lines).4 *5 * Copyright (c) 1989 Regents of the University of California.6 * All rights reserved.7 *8 * Redistribution and use in source and binary forms are permitted9 * provided that the above copyright notice and this paragraph are10 * duplicated in all such forms and that any documentation,11 * advertising materials, and other materials related to such12 * distribution and use acknowledge that the software was developed13 * by the University of California, Berkeley. The name of the14 * University may not be used to endorse or promote products derived15 * from this software without specific prior written permission.16 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR17 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.19 *20 * Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:21 * - Initial distribution.22 *23 *24 * modified for KA9Q Internet Software Package by25 * Katie Stevens (dkstevens@ucdavis.edu)26 * University of California, Davis27 * Computing Services28 * - 01-31-90 initial adaptation (from 1.19)29 * PPP.05 02-15-90 [ks]30 * PPP.08 05-02-90 [ks] use PPP protocol field to signal compression31 * PPP.15 09-90 [ks] improve mbuf handling32 * PPP.16 11-02 [karn] substantially rewritten to use NOS facilities33 *34 * - Feb 1991 Bill_Simpson@um.cc.umich.edu35 * variable number of conversation slots36 * allow zero or one slots37 * separate routines38 * status display39 * - Jul 1994 Dmitry Gorodchanin40 * Fixes for memory leaks.41 * - Oct 1994 Dmitry Gorodchanin42 * Modularization.43 * - Jan 1995 Bjorn Ekwall44 * Use ip_fast_csum from ip.h45 * - July 1995 Christos A. Polyzols46 * Spotted bug in tcp option checking47 *48 *49 * This module is a difficult issue. It's clearly inet code but it's also clearly50 * driver code belonging close to PPP and SLIP51 */52 53#include <linux/module.h>54#include <linux/slab.h>55#include <linux/types.h>56#include <linux/string.h>57#include <linux/errno.h>58#include <linux/kernel.h>59#include <net/slhc_vj.h>60 61#ifdef CONFIG_INET62/* Entire module is for IP only */63#include <linux/mm.h>64#include <linux/socket.h>65#include <linux/sockios.h>66#include <linux/termios.h>67#include <linux/in.h>68#include <linux/fcntl.h>69#include <linux/inet.h>70#include <linux/netdevice.h>71#include <net/ip.h>72#include <net/protocol.h>73#include <net/icmp.h>74#include <net/tcp.h>75#include <linux/skbuff.h>76#include <net/sock.h>77#include <linux/timer.h>78#include <linux/uaccess.h>79#include <net/checksum.h>80#include <linux/unaligned.h>81 82static unsigned char *encode(unsigned char *cp, unsigned short n);83static long decode(unsigned char **cpp);84static unsigned char * put16(unsigned char *cp, unsigned short x);85static unsigned short pull16(unsigned char **cpp);86 87/* Allocate compression data structure88 * slots must be in range 0 to 255 (zero meaning no compression)89 * Returns pointer to structure or ERR_PTR() on error.90 */91struct slcompress *92slhc_init(int rslots, int tslots)93{94 short i;95 struct cstate *ts;96 struct slcompress *comp;97 98 if (rslots < 0 || rslots > 255 || tslots < 0 || tslots > 255)99 return ERR_PTR(-EINVAL);100 101 comp = kzalloc(sizeof(struct slcompress), GFP_KERNEL);102 if (! comp)103 goto out_fail;104 105 if (rslots > 0) {106 size_t rsize = rslots * sizeof(struct cstate);107 comp->rstate = kzalloc(rsize, GFP_KERNEL);108 if (! comp->rstate)109 goto out_free;110 comp->rslot_limit = rslots - 1;111 }112 113 if (tslots > 0) {114 size_t tsize = tslots * sizeof(struct cstate);115 comp->tstate = kzalloc(tsize, GFP_KERNEL);116 if (! comp->tstate)117 goto out_free2;118 comp->tslot_limit = tslots - 1;119 }120 121 comp->xmit_oldest = 0;122 comp->xmit_current = 255;123 comp->recv_current = 255;124 /*125 * don't accept any packets with implicit index until we get126 * one with an explicit index. Otherwise the uncompress code127 * will try to use connection 255, which is almost certainly128 * out of range129 */130 comp->flags |= SLF_TOSS;131 132 if ( tslots > 0 ) {133 ts = comp->tstate;134 for(i = comp->tslot_limit; i > 0; --i){135 ts[i].cs_this = i;136 ts[i].next = &(ts[i - 1]);137 }138 ts[0].next = &(ts[comp->tslot_limit]);139 ts[0].cs_this = 0;140 }141 return comp;142 143out_free2:144 kfree(comp->rstate);145out_free:146 kfree(comp);147out_fail:148 return ERR_PTR(-ENOMEM);149}150 151 152/* Free a compression data structure */153void154slhc_free(struct slcompress *comp)155{156 if ( IS_ERR_OR_NULL(comp) )157 return;158 159 if ( comp->tstate != NULLSLSTATE )160 kfree( comp->tstate );161 162 if ( comp->rstate != NULLSLSTATE )163 kfree( comp->rstate );164 165 kfree( comp );166}167 168 169/* Put a short in host order into a char array in network order */170static inline unsigned char *171put16(unsigned char *cp, unsigned short x)172{173 *cp++ = x >> 8;174 *cp++ = x;175 176 return cp;177}178 179 180/* Encode a number */181static unsigned char *182encode(unsigned char *cp, unsigned short n)183{184 if(n >= 256 || n == 0){185 *cp++ = 0;186 cp = put16(cp,n);187 } else {188 *cp++ = n;189 }190 return cp;191}192 193/* Pull a 16-bit integer in host order from buffer in network byte order */194static unsigned short195pull16(unsigned char **cpp)196{197 short rval;198 199 rval = *(*cpp)++;200 rval <<= 8;201 rval |= *(*cpp)++;202 return rval;203}204 205/* Decode a number */206static long207decode(unsigned char **cpp)208{209 int x;210 211 x = *(*cpp)++;212 if(x == 0){213 return pull16(cpp) & 0xffff; /* pull16 returns -1 on error */214 } else {215 return x & 0xff; /* -1 if PULLCHAR returned error */216 }217}218 219/*220 * icp and isize are the original packet.221 * ocp is a place to put a copy if necessary.222 * cpp is initially a pointer to icp. If the copy is used,223 * change it to ocp.224 */225 226int227slhc_compress(struct slcompress *comp, unsigned char *icp, int isize,228 unsigned char *ocp, unsigned char **cpp, int compress_cid)229{230 struct cstate *ocs = &(comp->tstate[comp->xmit_oldest]);231 struct cstate *lcs = ocs;232 struct cstate *cs = lcs->next;233 unsigned long deltaS, deltaA;234 short changes = 0;235 int nlen, hlen;236 unsigned char new_seq[16];237 unsigned char *cp = new_seq;238 struct iphdr *ip;239 struct tcphdr *th, *oth;240 __sum16 csum;241 242 243 /*244 * Don't play with runt packets.245 */246 247 if(isize<sizeof(struct iphdr))248 return isize;249 250 ip = (struct iphdr *) icp;251 if (ip->version != 4 || ip->ihl < 5)252 return isize;253 254 /* Bail if this packet isn't TCP, or is an IP fragment */255 if (ip->protocol != IPPROTO_TCP || (ntohs(ip->frag_off) & 0x3fff)) {256 /* Send as regular IP */257 if(ip->protocol != IPPROTO_TCP)258 comp->sls_o_nontcp++;259 else260 comp->sls_o_tcp++;261 return isize;262 }263 nlen = ip->ihl * 4;264 if (isize < nlen + sizeof(*th))265 return isize;266 267 th = (struct tcphdr *)(icp + nlen);268 if (th->doff < sizeof(struct tcphdr) / 4)269 return isize;270 hlen = nlen + th->doff * 4;271 272 /* Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or273 * some other control bit is set). Also uncompressible if274 * it's a runt.275 */276 if(hlen > isize || th->syn || th->fin || th->rst ||277 ! (th->ack)){278 /* TCP connection stuff; send as regular IP */279 comp->sls_o_tcp++;280 return isize;281 }282 /*283 * Packet is compressible -- we're going to send either a284 * COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way,285 * we need to locate (or create) the connection state.286 *287 * States are kept in a circularly linked list with288 * xmit_oldest pointing to the end of the list. The289 * list is kept in lru order by moving a state to the290 * head of the list whenever it is referenced. Since291 * the list is short and, empirically, the connection292 * we want is almost always near the front, we locate293 * states via linear search. If we don't find a state294 * for the datagram, the oldest state is (re-)used.295 */296 for ( ; ; ) {297 if( ip->saddr == cs->cs_ip.saddr298 && ip->daddr == cs->cs_ip.daddr299 && th->source == cs->cs_tcp.source300 && th->dest == cs->cs_tcp.dest)301 goto found;302 303 /* if current equal oldest, at end of list */304 if ( cs == ocs )305 break;306 lcs = cs;307 cs = cs->next;308 comp->sls_o_searches++;309 }310 /*311 * Didn't find it -- re-use oldest cstate. Send an312 * uncompressed packet that tells the other side what313 * connection number we're using for this conversation.314 *315 * Note that since the state list is circular, the oldest316 * state points to the newest and we only need to set317 * xmit_oldest to update the lru linkage.318 */319 comp->sls_o_misses++;320 comp->xmit_oldest = lcs->cs_this;321 goto uncompressed;322 323found:324 /*325 * Found it -- move to the front on the connection list.326 */327 if(lcs == ocs) {328 /* found at most recently used */329 } else if (cs == ocs) {330 /* found at least recently used */331 comp->xmit_oldest = lcs->cs_this;332 } else {333 /* more than 2 elements */334 lcs->next = cs->next;335 cs->next = ocs->next;336 ocs->next = cs;337 }338 339 /*340 * Make sure that only what we expect to change changed.341 * Check the following:342 * IP protocol version, header length & type of service.343 * The "Don't fragment" bit.344 * The time-to-live field.345 * The TCP header length.346 * IP options, if any.347 * TCP options, if any.348 * If any of these things are different between the previous &349 * current datagram, we send the current datagram `uncompressed'.350 */351 oth = &cs->cs_tcp;352 353 if(ip->version != cs->cs_ip.version || ip->ihl != cs->cs_ip.ihl354 || ip->tos != cs->cs_ip.tos355 || (ip->frag_off & htons(0x4000)) != (cs->cs_ip.frag_off & htons(0x4000))356 || ip->ttl != cs->cs_ip.ttl357 || th->doff != cs->cs_tcp.doff358 || (ip->ihl > 5 && memcmp(ip+1,cs->cs_ipopt,((ip->ihl)-5)*4) != 0)359 || (th->doff > 5 && memcmp(th+1,cs->cs_tcpopt,((th->doff)-5)*4) != 0)){360 goto uncompressed;361 }362 363 /*364 * Figure out which of the changing fields changed. The365 * receiver expects changes in the order: urgent, window,366 * ack, seq (the order minimizes the number of temporaries367 * needed in this section of code).368 */369 if(th->urg){370 deltaS = ntohs(th->urg_ptr);371 cp = encode(cp,deltaS);372 changes |= NEW_U;373 } else if(th->urg_ptr != oth->urg_ptr){374 /* argh! URG not set but urp changed -- a sensible375 * implementation should never do this but RFC793376 * doesn't prohibit the change so we have to deal377 * with it. */378 goto uncompressed;379 }380 if((deltaS = ntohs(th->window) - ntohs(oth->window)) != 0){381 cp = encode(cp,deltaS);382 changes |= NEW_W;383 }384 if((deltaA = ntohl(th->ack_seq) - ntohl(oth->ack_seq)) != 0L){385 if(deltaA > 0x0000ffff)386 goto uncompressed;387 cp = encode(cp,deltaA);388 changes |= NEW_A;389 }390 if((deltaS = ntohl(th->seq) - ntohl(oth->seq)) != 0L){391 if(deltaS > 0x0000ffff)392 goto uncompressed;393 cp = encode(cp,deltaS);394 changes |= NEW_S;395 }396 397 switch(changes){398 case 0: /* Nothing changed. If this packet contains data and the399 * last one didn't, this is probably a data packet following400 * an ack (normal on an interactive connection) and we send401 * it compressed. Otherwise it's probably a retransmit,402 * retransmitted ack or window probe. Send it uncompressed403 * in case the other side missed the compressed version.404 */405 if(ip->tot_len != cs->cs_ip.tot_len &&406 ntohs(cs->cs_ip.tot_len) == hlen)407 break;408 goto uncompressed;409 case SPECIAL_I:410 case SPECIAL_D:411 /* actual changes match one of our special case encodings --412 * send packet uncompressed.413 */414 goto uncompressed;415 case NEW_S|NEW_A:416 if(deltaS == deltaA &&417 deltaS == ntohs(cs->cs_ip.tot_len) - hlen){418 /* special case for echoed terminal traffic */419 changes = SPECIAL_I;420 cp = new_seq;421 }422 break;423 case NEW_S:424 if(deltaS == ntohs(cs->cs_ip.tot_len) - hlen){425 /* special case for data xfer */426 changes = SPECIAL_D;427 cp = new_seq;428 }429 break;430 }431 deltaS = ntohs(ip->id) - ntohs(cs->cs_ip.id);432 if(deltaS != 1){433 cp = encode(cp,deltaS);434 changes |= NEW_I;435 }436 if(th->psh)437 changes |= TCP_PUSH_BIT;438 /* Grab the cksum before we overwrite it below. Then update our439 * state with this packet's header.440 */441 csum = th->check;442 memcpy(&cs->cs_ip,ip,20);443 memcpy(&cs->cs_tcp,th,20);444 /* We want to use the original packet as our compressed packet.445 * (cp - new_seq) is the number of bytes we need for compressed446 * sequence numbers. In addition we need one byte for the change447 * mask, one for the connection id and two for the tcp checksum.448 * So, (cp - new_seq) + 4 bytes of header are needed.449 */450 deltaS = cp - new_seq;451 if(compress_cid == 0 || comp->xmit_current != cs->cs_this){452 cp = ocp;453 *cpp = ocp;454 *cp++ = changes | NEW_C;455 *cp++ = cs->cs_this;456 comp->xmit_current = cs->cs_this;457 } else {458 cp = ocp;459 *cpp = ocp;460 *cp++ = changes;461 }462 *(__sum16 *)cp = csum;463 cp += 2;464/* deltaS is now the size of the change section of the compressed header */465 memcpy(cp,new_seq,deltaS); /* Write list of deltas */466 memcpy(cp+deltaS,icp+hlen,isize-hlen);467 comp->sls_o_compressed++;468 ocp[0] |= SL_TYPE_COMPRESSED_TCP;469 return isize - hlen + deltaS + (cp - ocp);470 471 /* Update connection state cs & send uncompressed packet (i.e.,472 * a regular ip/tcp packet but with the 'conversation id' we hope473 * to use on future compressed packets in the protocol field).474 */475uncompressed:476 memcpy(&cs->cs_ip,ip,20);477 memcpy(&cs->cs_tcp,th,20);478 if (ip->ihl > 5)479 memcpy(cs->cs_ipopt, ip+1, ((ip->ihl) - 5) * 4);480 if (th->doff > 5)481 memcpy(cs->cs_tcpopt, th+1, ((th->doff) - 5) * 4);482 comp->xmit_current = cs->cs_this;483 comp->sls_o_uncompressed++;484 memcpy(ocp, icp, isize);485 *cpp = ocp;486 ocp[9] = cs->cs_this;487 ocp[0] |= SL_TYPE_UNCOMPRESSED_TCP;488 return isize;489}490 491 492int493slhc_uncompress(struct slcompress *comp, unsigned char *icp, int isize)494{495 int changes;496 long x;497 struct tcphdr *thp;498 struct iphdr *ip;499 struct cstate *cs;500 int len, hdrlen;501 unsigned char *cp = icp;502 503 /* We've got a compressed packet; read the change byte */504 comp->sls_i_compressed++;505 if(isize < 3){506 comp->sls_i_error++;507 return 0;508 }509 changes = *cp++;510 if(changes & NEW_C){511 /* Make sure the state index is in range, then grab the state.512 * If we have a good state index, clear the 'discard' flag.513 */514 x = *cp++; /* Read conn index */515 if(x < 0 || x > comp->rslot_limit)516 goto bad;517 518 /* Check if the cstate is initialized */519 if (!comp->rstate[x].initialized)520 goto bad;521 522 comp->flags &=~ SLF_TOSS;523 comp->recv_current = x;524 } else {525 /* this packet has an implicit state index. If we've526 * had a line error since the last time we got an527 * explicit state index, we have to toss the packet. */528 if(comp->flags & SLF_TOSS){529 comp->sls_i_tossed++;530 return 0;531 }532 }533 cs = &comp->rstate[comp->recv_current];534 thp = &cs->cs_tcp;535 ip = &cs->cs_ip;536 537 thp->check = *(__sum16 *)cp;538 cp += 2;539 540 thp->psh = (changes & TCP_PUSH_BIT) ? 1 : 0;541/*542 * we can use the same number for the length of the saved header and543 * the current one, because the packet wouldn't have been sent544 * as compressed unless the options were the same as the previous one545 */546 547 hdrlen = ip->ihl * 4 + thp->doff * 4;548 549 switch(changes & SPECIALS_MASK){550 case SPECIAL_I: /* Echoed terminal traffic */551 {552 short i;553 i = ntohs(ip->tot_len) - hdrlen;554 thp->ack_seq = htonl( ntohl(thp->ack_seq) + i);555 thp->seq = htonl( ntohl(thp->seq) + i);556 }557 break;558 559 case SPECIAL_D: /* Unidirectional data */560 thp->seq = htonl( ntohl(thp->seq) +561 ntohs(ip->tot_len) - hdrlen);562 break;563 564 default:565 if(changes & NEW_U){566 thp->urg = 1;567 if((x = decode(&cp)) == -1) {568 goto bad;569 }570 thp->urg_ptr = htons(x);571 } else572 thp->urg = 0;573 if(changes & NEW_W){574 if((x = decode(&cp)) == -1) {575 goto bad;576 }577 thp->window = htons( ntohs(thp->window) + x);578 }579 if(changes & NEW_A){580 if((x = decode(&cp)) == -1) {581 goto bad;582 }583 thp->ack_seq = htonl( ntohl(thp->ack_seq) + x);584 }585 if(changes & NEW_S){586 if((x = decode(&cp)) == -1) {587 goto bad;588 }589 thp->seq = htonl( ntohl(thp->seq) + x);590 }591 break;592 }593 if(changes & NEW_I){594 if((x = decode(&cp)) == -1) {595 goto bad;596 }597 ip->id = htons (ntohs (ip->id) + x);598 } else599 ip->id = htons (ntohs (ip->id) + 1);600 601 /*602 * At this point, cp points to the first byte of data in the603 * packet. Put the reconstructed TCP and IP headers back on the604 * packet. Recalculate IP checksum (but not TCP checksum).605 */606 607 len = isize - (cp - icp);608 if (len < 0)609 goto bad;610 len += hdrlen;611 ip->tot_len = htons(len);612 ip->check = 0;613 614 memmove(icp + hdrlen, cp, len - hdrlen);615 616 cp = icp;617 memcpy(cp, ip, 20);618 cp += 20;619 620 if (ip->ihl > 5) {621 memcpy(cp, cs->cs_ipopt, (ip->ihl - 5) * 4);622 cp += (ip->ihl - 5) * 4;623 }624 625 put_unaligned(ip_fast_csum(icp, ip->ihl),626 &((struct iphdr *)icp)->check);627 628 memcpy(cp, thp, 20);629 cp += 20;630 631 if (thp->doff > 5) {632 memcpy(cp, cs->cs_tcpopt, ((thp->doff) - 5) * 4);633 cp += ((thp->doff) - 5) * 4;634 }635 636 return len;637bad:638 comp->sls_i_error++;639 return slhc_toss( comp );640}641 642 643int644slhc_remember(struct slcompress *comp, unsigned char *icp, int isize)645{646 const struct tcphdr *th;647 unsigned char index;648 struct iphdr *iph;649 struct cstate *cs;650 unsigned int ihl;651 652 /* The packet is shorter than a legal IP header.653 * Also make sure isize is positive.654 */655 if (isize < (int)sizeof(struct iphdr)) {656runt:657 comp->sls_i_runt++;658 return slhc_toss(comp);659 }660 iph = (struct iphdr *)icp;661 /* Peek at the IP header's IHL field to find its length */662 ihl = iph->ihl;663 /* The IP header length field is too small,664 * or packet is shorter than the IP header followed665 * by minimal tcp header.666 */667 if (ihl < 5 || isize < ihl * 4 + sizeof(struct tcphdr))668 goto runt;669 670 index = iph->protocol;671 iph->protocol = IPPROTO_TCP;672 673 if (ip_fast_csum(icp, ihl)) {674 /* Bad IP header checksum; discard */675 comp->sls_i_badcheck++;676 return slhc_toss(comp);677 }678 if (index > comp->rslot_limit) {679 comp->sls_i_error++;680 return slhc_toss(comp);681 }682 th = (struct tcphdr *)(icp + ihl * 4);683 if (th->doff < sizeof(struct tcphdr) / 4)684 goto runt;685 if (isize < ihl * 4 + th->doff * 4)686 goto runt;687 /* Update local state */688 cs = &comp->rstate[comp->recv_current = index];689 comp->flags &=~ SLF_TOSS;690 memcpy(&cs->cs_ip, iph, sizeof(*iph));691 memcpy(&cs->cs_tcp, th, sizeof(*th));692 if (ihl > 5)693 memcpy(cs->cs_ipopt, &iph[1], (ihl - 5) * 4);694 if (th->doff > 5)695 memcpy(cs->cs_tcpopt, &th[1], (th->doff - 5) * 4);696 cs->cs_hsize = ihl*2 + th->doff*2;697 cs->initialized = true;698 /* Put headers back on packet699 * Neither header checksum is recalculated700 */701 comp->sls_i_uncompressed++;702 return isize;703}704 705int706slhc_toss(struct slcompress *comp)707{708 if ( comp == NULLSLCOMPR )709 return 0;710 711 comp->flags |= SLF_TOSS;712 return 0;713}714 715#else /* CONFIG_INET */716 717int718slhc_toss(struct slcompress *comp)719{720 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_toss");721 return -EINVAL;722}723int724slhc_uncompress(struct slcompress *comp, unsigned char *icp, int isize)725{726 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_uncompress");727 return -EINVAL;728}729int730slhc_compress(struct slcompress *comp, unsigned char *icp, int isize,731 unsigned char *ocp, unsigned char **cpp, int compress_cid)732{733 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_compress");734 return -EINVAL;735}736 737int738slhc_remember(struct slcompress *comp, unsigned char *icp, int isize)739{740 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_remember");741 return -EINVAL;742}743 744void745slhc_free(struct slcompress *comp)746{747 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_free");748}749struct slcompress *750slhc_init(int rslots, int tslots)751{752 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_init");753 return NULL;754}755 756#endif /* CONFIG_INET */757 758/* VJ header compression */759EXPORT_SYMBOL(slhc_init);760EXPORT_SYMBOL(slhc_free);761EXPORT_SYMBOL(slhc_remember);762EXPORT_SYMBOL(slhc_compress);763EXPORT_SYMBOL(slhc_uncompress);764EXPORT_SYMBOL(slhc_toss);765 766MODULE_DESCRIPTION("Compression helpers for SLIP (serial line)");767MODULE_LICENSE("Dual BSD/GPL");768