2 * Routines to compress and uncompress tcp packets (for transmission
3 * over low speed serial lines).
5 * Copyright (c) 1989 Regents of the University of California.
8 * Redistribution and use in source and binary forms are permitted
9 * provided that the above copyright notice and this paragraph are
10 * duplicated in all such forms and that any documentation,
11 * advertising materials, and other materials related to such
12 * distribution and use acknowledge that the software was developed
13 * by the University of California, Berkeley. The name of the
14 * University may not be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
17 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
20 * Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
21 * - Initial distribution.
24 * modified for KA9Q Internet Software Package by
25 * Katie Stevens (dkstevens@ucdavis.edu)
26 * University of California, Davis
28 * - 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 compression
31 * PPP.15 09-90 [ks] improve mbuf handling
32 * PPP.16 11-02 [karn] substantially rewritten to use NOS facilities
34 * - Feb 1991 Bill_Simpson@um.cc.umich.edu
35 * variable number of conversation slots
36 * allow zero or one slots
39 * - Jul 1994 Dmitry Gorodchanin
40 * Fixes for memory leaks.
41 * - Oct 1994 Dmitry Gorodchanin
43 * - Jan 1995 Bjorn Ekwall
44 * Use ip_fast_csum from ip.h
45 * - July 1995 Christos A. Polyzols
46 * Spotted bug in tcp option checking
49 * This module is a difficult issue. It's clearly inet code but it's also clearly
50 * driver code belonging close to PPP and SLIP
53 #include <linux/config.h>
54 #include <linux/module.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>
62 /* Entire module is for IP only */
63 #include <linux/sched.h>
65 #include <linux/socket.h>
66 #include <linux/sockios.h>
67 #include <linux/termios.h>
69 #include <linux/fcntl.h>
70 #include <linux/inet.h>
71 #include <linux/netdevice.h>
73 #include <net/protocol.h>
76 #include <linux/skbuff.h>
78 #include <linux/timer.h>
79 #include <asm/system.h>
80 #include <asm/uaccess.h>
81 #include <net/checksum.h>
82 #include <asm/unaligned.h>
84 static unsigned char *encode(unsigned char *cp, unsigned short n);
85 static long decode(unsigned char **cpp);
86 static unsigned char * put16(unsigned char *cp, unsigned short x);
87 static unsigned short pull16(unsigned char **cpp);
89 /* Initialize compression data structure
90 * slots must be in range 0 to 255 (zero meaning no compression)
93 slhc_init(int rslots, int tslots)
96 register struct cstate *ts;
97 struct slcompress *comp;
100 comp = (struct slcompress *)kmalloc(sizeof(struct slcompress),
104 memset(comp, 0, sizeof(struct slcompress));
106 if ( rslots > 0 && rslots < 256 ) {
107 size_t rsize = rslots * sizeof(struct cstate);
108 comp->rstate = (struct cstate *) kmalloc(rsize, GFP_KERNEL);
111 memset(comp->rstate, 0, rsize);
112 comp->rslot_limit = rslots - 1;
115 if ( tslots > 0 && tslots < 256 ) {
116 size_t tsize = tslots * sizeof(struct cstate);
117 comp->tstate = (struct cstate *) kmalloc(tsize, GFP_KERNEL);
120 memset(comp->tstate, 0, tsize);
121 comp->tslot_limit = tslots - 1;
124 comp->xmit_oldest = 0;
125 comp->xmit_current = 255;
126 comp->recv_current = 255;
128 * don't accept any packets with implicit index until we get
129 * one with an explicit index. Otherwise the uncompress code
130 * will try to use connection 255, which is almost certainly
133 comp->flags |= SLF_TOSS;
137 for(i = comp->tslot_limit; i > 0; --i){
139 ts[i].next = &(ts[i - 1]);
141 ts[0].next = &(ts[comp->tslot_limit]);
147 kfree((unsigned char *)comp->rstate);
149 kfree((unsigned char *)comp);
156 /* Free a compression data structure */
158 slhc_free(struct slcompress *comp)
160 if ( comp == NULLSLCOMPR )
163 if ( comp->tstate != NULLSLSTATE )
164 kfree( comp->tstate );
166 if ( comp->rstate != NULLSLSTATE )
167 kfree( comp->rstate );
174 /* Put a short in host order into a char array in network order */
175 static inline unsigned char *
176 put16(unsigned char *cp, unsigned short x)
185 /* Encode a number */
187 encode(unsigned char *cp, unsigned short n)
189 if(n >= 256 || n == 0){
198 /* Pull a 16-bit integer in host order from buffer in network byte order */
199 static unsigned short
200 pull16(unsigned char **cpp)
210 /* Decode a number */
212 decode(unsigned char **cpp)
218 return pull16(cpp) & 0xffff; /* pull16 returns -1 on error */
220 return x & 0xff; /* -1 if PULLCHAR returned error */
225 * icp and isize are the original packet.
226 * ocp is a place to put a copy if necessary.
227 * cpp is initially a pointer to icp. If the copy is used,
232 slhc_compress(struct slcompress *comp, unsigned char *icp, int isize,
233 unsigned char *ocp, unsigned char **cpp, int compress_cid)
235 register struct cstate *ocs = &(comp->tstate[comp->xmit_oldest]);
236 register struct cstate *lcs = ocs;
237 register struct cstate *cs = lcs->next;
238 register unsigned long deltaS, deltaA;
239 register short changes = 0;
241 unsigned char new_seq[16];
242 register unsigned char *cp = new_seq;
244 struct tcphdr *th, *oth;
248 * Don't play with runt packets.
251 if(isize<sizeof(struct iphdr))
254 ip = (struct iphdr *) icp;
256 /* Bail if this packet isn't TCP, or is an IP fragment */
257 if (ip->protocol != IPPROTO_TCP || (ntohs(ip->frag_off) & 0x3fff)) {
258 /* Send as regular IP */
259 if(ip->protocol != IPPROTO_TCP)
260 comp->sls_o_nontcp++;
265 /* Extract TCP header */
267 th = (struct tcphdr *)(((unsigned char *)ip) + ip->ihl*4);
268 hlen = ip->ihl*4 + th->doff*4;
270 /* Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
271 * some other control bit is set). Also uncompressible if
274 if(hlen > isize || th->syn || th->fin || th->rst ||
276 /* TCP connection stuff; send as regular IP */
281 * Packet is compressible -- we're going to send either a
282 * COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way,
283 * we need to locate (or create) the connection state.
285 * States are kept in a circularly linked list with
286 * xmit_oldest pointing to the end of the list. The
287 * list is kept in lru order by moving a state to the
288 * head of the list whenever it is referenced. Since
289 * the list is short and, empirically, the connection
290 * we want is almost always near the front, we locate
291 * states via linear search. If we don't find a state
292 * for the datagram, the oldest state is (re-)used.
295 if( ip->saddr == cs->cs_ip.saddr
296 && ip->daddr == cs->cs_ip.daddr
297 && th->source == cs->cs_tcp.source
298 && th->dest == cs->cs_tcp.dest)
301 /* if current equal oldest, at end of list */
306 comp->sls_o_searches++;
309 * Didn't find it -- re-use oldest cstate. Send an
310 * uncompressed packet that tells the other side what
311 * connection number we're using for this conversation.
313 * Note that since the state list is circular, the oldest
314 * state points to the newest and we only need to set
315 * xmit_oldest to update the lru linkage.
317 comp->sls_o_misses++;
318 comp->xmit_oldest = lcs->cs_this;
323 * Found it -- move to the front on the connection list.
326 /* found at most recently used */
327 } else if (cs == ocs) {
328 /* found at least recently used */
329 comp->xmit_oldest = lcs->cs_this;
331 /* more than 2 elements */
332 lcs->next = cs->next;
333 cs->next = ocs->next;
338 * Make sure that only what we expect to change changed.
339 * Check the following:
340 * IP protocol version, header length & type of service.
341 * The "Don't fragment" bit.
342 * The time-to-live field.
343 * The TCP header length.
344 * IP options, if any.
345 * TCP options, if any.
346 * If any of these things are different between the previous &
347 * current datagram, we send the current datagram `uncompressed'.
351 if(ip->version != cs->cs_ip.version || ip->ihl != cs->cs_ip.ihl
352 || ip->tos != cs->cs_ip.tos
353 || (ip->frag_off & htons(0x4000)) != (cs->cs_ip.frag_off & htons(0x4000))
354 || ip->ttl != cs->cs_ip.ttl
355 || th->doff != cs->cs_tcp.doff
356 || (ip->ihl > 5 && memcmp(ip+1,cs->cs_ipopt,((ip->ihl)-5)*4) != 0)
357 || (th->doff > 5 && memcmp(th+1,cs->cs_tcpopt,((th->doff)-5)*4) != 0)){
362 * Figure out which of the changing fields changed. The
363 * receiver expects changes in the order: urgent, window,
364 * ack, seq (the order minimizes the number of temporaries
365 * needed in this section of code).
368 deltaS = ntohs(th->urg_ptr);
369 cp = encode(cp,deltaS);
371 } else if(th->urg_ptr != oth->urg_ptr){
372 /* argh! URG not set but urp changed -- a sensible
373 * implementation should never do this but RFC793
374 * doesn't prohibit the change so we have to deal
378 if((deltaS = ntohs(th->window) - ntohs(oth->window)) != 0){
379 cp = encode(cp,deltaS);
382 if((deltaA = ntohl(th->ack_seq) - ntohl(oth->ack_seq)) != 0L){
383 if(deltaA > 0x0000ffff)
385 cp = encode(cp,deltaA);
388 if((deltaS = ntohl(th->seq) - ntohl(oth->seq)) != 0L){
389 if(deltaS > 0x0000ffff)
391 cp = encode(cp,deltaS);
396 case 0: /* Nothing changed. If this packet contains data and the
397 * last one didn't, this is probably a data packet following
398 * an ack (normal on an interactive connection) and we send
399 * it compressed. Otherwise it's probably a retransmit,
400 * retransmitted ack or window probe. Send it uncompressed
401 * in case the other side missed the compressed version.
403 if(ip->tot_len != cs->cs_ip.tot_len &&
404 ntohs(cs->cs_ip.tot_len) == hlen)
410 /* actual changes match one of our special case encodings --
411 * send packet uncompressed.
415 if(deltaS == deltaA &&
416 deltaS == ntohs(cs->cs_ip.tot_len) - hlen){
417 /* special case for echoed terminal traffic */
423 if(deltaS == ntohs(cs->cs_ip.tot_len) - hlen){
424 /* special case for data xfer */
430 deltaS = ntohs(ip->id) - ntohs(cs->cs_ip.id);
432 cp = encode(cp,deltaS);
436 changes |= TCP_PUSH_BIT;
437 /* Grab the cksum before we overwrite it below. Then update our
438 * state with this packet's header.
440 deltaA = ntohs(th->check);
441 memcpy(&cs->cs_ip,ip,20);
442 memcpy(&cs->cs_tcp,th,20);
443 /* We want to use the original packet as our compressed packet.
444 * (cp - new_seq) is the number of bytes we need for compressed
445 * sequence numbers. In addition we need one byte for the change
446 * mask, one for the connection id and two for the tcp checksum.
447 * So, (cp - new_seq) + 4 bytes of header are needed.
449 deltaS = cp - new_seq;
450 if(compress_cid == 0 || comp->xmit_current != cs->cs_this){
453 *cp++ = changes | NEW_C;
455 comp->xmit_current = cs->cs_this;
461 cp = put16(cp,(short)deltaA); /* Write TCP checksum */
462 /* deltaS is now the size of the change section of the compressed header */
463 memcpy(cp,new_seq,deltaS); /* Write list of deltas */
464 memcpy(cp+deltaS,icp+hlen,isize-hlen);
465 comp->sls_o_compressed++;
466 ocp[0] |= SL_TYPE_COMPRESSED_TCP;
467 return isize - hlen + deltaS + (cp - ocp);
469 /* Update connection state cs & send uncompressed packet (i.e.,
470 * a regular ip/tcp packet but with the 'conversation id' we hope
471 * to use on future compressed packets in the protocol field).
474 memcpy(&cs->cs_ip,ip,20);
475 memcpy(&cs->cs_tcp,th,20);
477 memcpy(cs->cs_ipopt, ip+1, ((ip->ihl) - 5) * 4);
479 memcpy(cs->cs_tcpopt, th+1, ((th->doff) - 5) * 4);
480 comp->xmit_current = cs->cs_this;
481 comp->sls_o_uncompressed++;
482 memcpy(ocp, icp, isize);
484 ocp[9] = cs->cs_this;
485 ocp[0] |= SL_TYPE_UNCOMPRESSED_TCP;
491 slhc_uncompress(struct slcompress *comp, unsigned char *icp, int isize)
493 register int changes;
495 register struct tcphdr *thp;
496 register struct iphdr *ip;
497 register struct cstate *cs;
499 unsigned char *cp = icp;
501 /* We've got a compressed packet; read the change byte */
502 comp->sls_i_compressed++;
509 /* Make sure the state index is in range, then grab the state.
510 * If we have a good state index, clear the 'discard' flag.
512 x = *cp++; /* Read conn index */
513 if(x < 0 || x > comp->rslot_limit)
516 comp->flags &=~ SLF_TOSS;
517 comp->recv_current = x;
519 /* this packet has an implicit state index. If we've
520 * had a line error since the last time we got an
521 * explicit state index, we have to toss the packet. */
522 if(comp->flags & SLF_TOSS){
523 comp->sls_i_tossed++;
527 cs = &comp->rstate[comp->recv_current];
531 if((x = pull16(&cp)) == -1) { /* Read the TCP checksum */
534 thp->check = htons(x);
536 thp->psh = (changes & TCP_PUSH_BIT) ? 1 : 0;
538 * we can use the same number for the length of the saved header and
539 * the current one, because the packet wouldn't have been sent
540 * as compressed unless the options were the same as the previous one
543 hdrlen = ip->ihl * 4 + thp->doff * 4;
545 switch(changes & SPECIALS_MASK){
546 case SPECIAL_I: /* Echoed terminal traffic */
549 i = ntohs(ip->tot_len) - hdrlen;
550 thp->ack_seq = htonl( ntohl(thp->ack_seq) + i);
551 thp->seq = htonl( ntohl(thp->seq) + i);
555 case SPECIAL_D: /* Unidirectional data */
556 thp->seq = htonl( ntohl(thp->seq) +
557 ntohs(ip->tot_len) - hdrlen);
563 if((x = decode(&cp)) == -1) {
566 thp->urg_ptr = htons(x);
570 if((x = decode(&cp)) == -1) {
573 thp->window = htons( ntohs(thp->window) + x);
576 if((x = decode(&cp)) == -1) {
579 thp->ack_seq = htonl( ntohl(thp->ack_seq) + x);
582 if((x = decode(&cp)) == -1) {
585 thp->seq = htonl( ntohl(thp->seq) + x);
590 if((x = decode(&cp)) == -1) {
593 ip->id = htons (ntohs (ip->id) + x);
595 ip->id = htons (ntohs (ip->id) + 1);
598 * At this point, cp points to the first byte of data in the
599 * packet. Put the reconstructed TCP and IP headers back on the
600 * packet. Recalculate IP checksum (but not TCP checksum).
603 len = isize - (cp - icp);
607 ip->tot_len = htons(len);
610 memmove(icp + hdrlen, cp, len - hdrlen);
617 memcpy(cp, cs->cs_ipopt, (ip->ihl - 5) * 4);
618 cp += (ip->ihl - 5) * 4;
621 put_unaligned(ip_fast_csum(icp, ip->ihl),
622 &((struct iphdr *)icp)->check);
628 memcpy(cp, cs->cs_tcpopt, ((thp->doff) - 5) * 4);
629 cp += ((thp->doff) - 5) * 4;
635 return slhc_toss( comp );
640 slhc_remember(struct slcompress *comp, unsigned char *icp, int isize)
642 register struct cstate *cs;
648 /* The packet is shorter than a legal IP header */
650 return slhc_toss( comp );
652 /* Peek at the IP header's IHL field to find its length */
655 /* The IP header length field is too small */
657 return slhc_toss( comp );
660 icp[9] = IPPROTO_TCP;
662 if (ip_fast_csum(icp, ihl)) {
663 /* Bad IP header checksum; discard */
664 comp->sls_i_badcheck++;
665 return slhc_toss( comp );
667 if(index > comp->rslot_limit) {
669 return slhc_toss(comp);
672 /* Update local state */
673 cs = &comp->rstate[comp->recv_current = index];
674 comp->flags &=~ SLF_TOSS;
675 memcpy(&cs->cs_ip,icp,20);
676 memcpy(&cs->cs_tcp,icp + ihl*4,20);
678 memcpy(cs->cs_ipopt, icp + sizeof(struct iphdr), (ihl - 5) * 4);
679 if (cs->cs_tcp.doff > 5)
680 memcpy(cs->cs_tcpopt, icp + ihl*4 + sizeof(struct tcphdr), (cs->cs_tcp.doff - 5) * 4);
681 cs->cs_hsize = ihl*2 + cs->cs_tcp.doff*2;
682 /* Put headers back on packet
683 * Neither header checksum is recalculated
685 comp->sls_i_uncompressed++;
691 slhc_toss(struct slcompress *comp)
693 if ( comp == NULLSLCOMPR )
696 comp->flags |= SLF_TOSS;
701 void slhc_i_status(struct slcompress *comp)
703 if (comp != NULLSLCOMPR) {
704 printk("\t%d Cmp, %d Uncmp, %d Bad, %d Tossed\n",
705 comp->sls_i_compressed,
706 comp->sls_i_uncompressed,
713 void slhc_o_status(struct slcompress *comp)
715 if (comp != NULLSLCOMPR) {
716 printk("\t%d Cmp, %d Uncmp, %d AsIs, %d NotTCP\n",
717 comp->sls_o_compressed,
718 comp->sls_o_uncompressed,
721 printk("\t%10d Searches, %10d Misses\n",
722 comp->sls_o_searches,
727 /* Should this be surrounded with "#ifdef CONFIG_MODULES" ? */
728 /* VJ header compression */
729 EXPORT_SYMBOL(slhc_init);
730 EXPORT_SYMBOL(slhc_free);
731 EXPORT_SYMBOL(slhc_remember);
732 EXPORT_SYMBOL(slhc_compress);
733 EXPORT_SYMBOL(slhc_uncompress);
734 EXPORT_SYMBOL(slhc_toss);
738 int init_module(void)
740 printk(KERN_INFO "CSLIP: code copyright 1989 Regents of the University of California\n");
744 void cleanup_module(void)
750 #else /* CONFIG_INET */
754 slhc_toss(struct slcompress *comp)
756 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_toss");
760 slhc_uncompress(struct slcompress *comp, unsigned char *icp, int isize)
762 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_uncompress");
766 slhc_compress(struct slcompress *comp, unsigned char *icp, int isize,
767 unsigned char *ocp, unsigned char **cpp, int compress_cid)
769 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_compress");
774 slhc_remember(struct slcompress *comp, unsigned char *icp, int isize)
776 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_remember");
781 slhc_free(struct slcompress *comp)
783 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_free");
787 slhc_init(int rslots, int tslots)
789 printk(KERN_DEBUG "Called IP function on non IP-system: slhc_init");
792 EXPORT_SYMBOL(slhc_init);
793 EXPORT_SYMBOL(slhc_free);
794 EXPORT_SYMBOL(slhc_remember);
795 EXPORT_SYMBOL(slhc_compress);
796 EXPORT_SYMBOL(slhc_uncompress);
797 EXPORT_SYMBOL(slhc_toss);
799 #endif /* CONFIG_INET */
800 MODULE_LICENSE("Dual BSD/GPL");