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>
61 /* Entire module is for IP only */
62 #include <linux/sched.h>
64 #include <linux/socket.h>
65 #include <linux/sockios.h>
66 #include <linux/termios.h>
68 #include <linux/fcntl.h>
69 #include <linux/inet.h>
70 #include <linux/netdevice.h>
72 #include <net/protocol.h>
75 #include <linux/skbuff.h>
77 #include <linux/timer.h>
78 #include <asm/system.h>
79 #include <asm/uaccess.h>
80 #include <linux/init.h>
81 #include <net/checksum.h>
82 #include <net/slhc_vj.h>
83 #include <asm/unaligned.h>
87 static unsigned char *encode(unsigned char *cp
, unsigned short n
);
88 static long decode(unsigned char **cpp
);
89 static unsigned char * put16(unsigned char *cp
, unsigned short x
);
90 static unsigned short pull16(unsigned char **cpp
);
92 /* Initialize compression data structure
93 * slots must be in range 0 to 255 (zero meaning no compression)
96 slhc_init(int rslots
, int tslots
)
99 register struct cstate
*ts
;
100 struct slcompress
*comp
;
103 comp
= (struct slcompress
*)kmalloc(sizeof(struct slcompress
),
107 memset(comp
, 0, sizeof(struct slcompress
));
109 if ( rslots
> 0 && rslots
< 256 ) {
110 size_t rsize
= rslots
* sizeof(struct cstate
);
111 comp
->rstate
= (struct cstate
*) kmalloc(rsize
, GFP_KERNEL
);
114 memset(comp
->rstate
, 0, rsize
);
115 comp
->rslot_limit
= rslots
- 1;
118 if ( tslots
> 0 && tslots
< 256 ) {
119 size_t tsize
= tslots
* sizeof(struct cstate
);
120 comp
->tstate
= (struct cstate
*) kmalloc(tsize
, GFP_KERNEL
);
123 memset(comp
->tstate
, 0, tsize
);
124 comp
->tslot_limit
= tslots
- 1;
127 comp
->xmit_oldest
= 0;
128 comp
->xmit_current
= 255;
129 comp
->recv_current
= 255;
131 * don't accept any packets with implicit index until we get
132 * one with an explicit index. Otherwise the uncompress code
133 * will try to use connection 255, which is almost certainly
136 comp
->flags
|= SLF_TOSS
;
140 for(i
= comp
->tslot_limit
; i
> 0; --i
){
142 ts
[i
].next
= &(ts
[i
- 1]);
144 ts
[0].next
= &(ts
[comp
->tslot_limit
]);
150 kfree((unsigned char *)comp
->rstate
);
152 kfree((unsigned char *)comp
);
159 /* Free a compression data structure */
161 slhc_free(struct slcompress
*comp
)
163 if ( comp
== NULLSLCOMPR
)
166 if ( comp
->tstate
!= NULLSLSTATE
)
167 kfree( comp
->tstate
);
169 if ( comp
->rstate
!= NULLSLSTATE
)
170 kfree( comp
->rstate
);
177 /* Put a short in host order into a char array in network order */
178 static inline unsigned char *
179 put16(unsigned char *cp
, unsigned short x
)
188 /* Encode a number */
190 encode(unsigned char *cp
, unsigned short n
)
192 if(n
>= 256 || n
== 0){
201 /* Pull a 16-bit integer in host order from buffer in network byte order */
202 static unsigned short
203 pull16(unsigned char **cpp
)
213 /* Decode a number */
215 decode(unsigned char **cpp
)
221 return pull16(cpp
) & 0xffff; /* pull16 returns -1 on error */
223 return x
& 0xff; /* -1 if PULLCHAR returned error */
228 * icp and isize are the original packet.
229 * ocp is a place to put a copy if necessary.
230 * cpp is initially a pointer to icp. If the copy is used,
235 slhc_compress(struct slcompress
*comp
, unsigned char *icp
, int isize
,
236 unsigned char *ocp
, unsigned char **cpp
, int compress_cid
)
238 register struct cstate
*ocs
= &(comp
->tstate
[comp
->xmit_oldest
]);
239 register struct cstate
*lcs
= ocs
;
240 register struct cstate
*cs
= lcs
->next
;
241 register unsigned long deltaS
, deltaA
;
242 register short changes
= 0;
244 unsigned char new_seq
[16];
245 register unsigned char *cp
= new_seq
;
247 struct tcphdr
*th
, *oth
;
251 * Don't play with runt packets.
254 if(isize
<sizeof(struct iphdr
))
257 ip
= (struct iphdr
*) icp
;
259 /* Bail if this packet isn't TCP, or is an IP fragment */
260 if(ip
->protocol
!= IPPROTO_TCP
|| (ntohs(ip
->frag_off
) & 0x1fff) ||
261 (ip
->frag_off
& 32)){
262 /* Send as regular IP */
263 if(ip
->protocol
!= IPPROTO_TCP
)
264 comp
->sls_o_nontcp
++;
269 /* Extract TCP header */
271 th
= (struct tcphdr
*)(((unsigned char *)ip
) + ip
->ihl
*4);
272 hlen
= ip
->ihl
*4 + th
->doff
*4;
274 /* Bail if the TCP packet isn't `compressible' (i.e., ACK isn't set or
275 * some other control bit is set). Also uncompressible if
278 if(hlen
> isize
|| th
->syn
|| th
->fin
|| th
->rst
||
280 /* TCP connection stuff; send as regular IP */
285 * Packet is compressible -- we're going to send either a
286 * COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way,
287 * we need to locate (or create) the connection state.
289 * States are kept in a circularly linked list with
290 * xmit_oldest pointing to the end of the list. The
291 * list is kept in lru order by moving a state to the
292 * head of the list whenever it is referenced. Since
293 * the list is short and, empirically, the connection
294 * we want is almost always near the front, we locate
295 * states via linear search. If we don't find a state
296 * for the datagram, the oldest state is (re-)used.
299 if( ip
->saddr
== cs
->cs_ip
.saddr
300 && ip
->daddr
== cs
->cs_ip
.daddr
301 && th
->source
== cs
->cs_tcp
.source
302 && th
->dest
== cs
->cs_tcp
.dest
)
305 /* if current equal oldest, at end of list */
310 comp
->sls_o_searches
++;
313 * Didn't find it -- re-use oldest cstate. Send an
314 * uncompressed packet that tells the other side what
315 * connection number we're using for this conversation.
317 * Note that since the state list is circular, the oldest
318 * state points to the newest and we only need to set
319 * xmit_oldest to update the lru linkage.
321 comp
->sls_o_misses
++;
322 comp
->xmit_oldest
= lcs
->cs_this
;
327 * Found it -- move to the front on the connection list.
330 /* found at most recently used */
331 } else if (cs
== ocs
) {
332 /* found at least recently used */
333 comp
->xmit_oldest
= lcs
->cs_this
;
335 /* more than 2 elements */
336 lcs
->next
= cs
->next
;
337 cs
->next
= ocs
->next
;
342 * Make sure that only what we expect to change changed.
343 * Check the following:
344 * IP protocol version, header length & type of service.
345 * The "Don't fragment" bit.
346 * The time-to-live field.
347 * The TCP header length.
348 * IP options, if any.
349 * TCP options, if any.
350 * If any of these things are different between the previous &
351 * current datagram, we send the current datagram `uncompressed'.
356 || ip
->version
!= cs
->cs_ip
.version
|| ip
->ihl
!= cs
->cs_ip
.ihl
357 || ip
->tos
!= cs
->cs_ip
.tos
358 || (ip
->frag_off
& 64) != (cs
->cs_ip
.frag_off
& 64)
359 || ip
->ttl
!= cs
->cs_ip
.ttl
360 || th
->doff
!= cs
->cs_tcp
.doff
361 || (ip
->ihl
> 5 && memcmp(ip
+1,cs
->cs_ipopt
,((ip
->ihl
)-5)*4) != 0)
362 || (th
->doff
> 5 && memcmp(th
+1,cs
->cs_tcpopt
,((th
->doff
)-5)*4) != 0)){
367 * Figure out which of the changing fields changed. The
368 * receiver expects changes in the order: urgent, window,
369 * ack, seq (the order minimizes the number of temporaries
370 * needed in this section of code).
373 deltaS
= ntohs(th
->urg_ptr
);
374 cp
= encode(cp
,deltaS
);
376 } else if(th
->urg_ptr
!= oth
->urg_ptr
){
377 /* argh! URG not set but urp changed -- a sensible
378 * implementation should never do this but RFC793
379 * doesn't prohibit the change so we have to deal
383 if((deltaS
= ntohs(th
->window
) - ntohs(oth
->window
)) != 0){
384 cp
= encode(cp
,deltaS
);
387 if((deltaA
= ntohl(th
->ack_seq
) - ntohl(oth
->ack_seq
)) != 0L){
388 if(deltaA
> 0x0000ffff)
390 cp
= encode(cp
,deltaA
);
393 if((deltaS
= ntohl(th
->seq
) - ntohl(oth
->seq
)) != 0L){
394 if(deltaS
> 0x0000ffff)
396 cp
= encode(cp
,deltaS
);
401 case 0: /* Nothing changed. If this packet contains data and the
402 * last one didn't, this is probably a data packet following
403 * an ack (normal on an interactive connection) and we send
404 * it compressed. Otherwise it's probably a retransmit,
405 * retransmitted ack or window probe. Send it uncompressed
406 * in case the other side missed the compressed version.
408 if(ip
->tot_len
!= cs
->cs_ip
.tot_len
&&
409 ntohs(cs
->cs_ip
.tot_len
) == hlen
)
415 /* actual changes match one of our special case encodings --
416 * send packet uncompressed.
420 if(deltaS
== deltaA
&&
421 deltaS
== ntohs(cs
->cs_ip
.tot_len
) - hlen
){
422 /* special case for echoed terminal traffic */
428 if(deltaS
== ntohs(cs
->cs_ip
.tot_len
) - hlen
){
429 /* special case for data xfer */
435 deltaS
= ntohs(ip
->id
) - ntohs(cs
->cs_ip
.id
);
437 cp
= encode(cp
,deltaS
);
441 changes
|= TCP_PUSH_BIT
;
442 /* Grab the cksum before we overwrite it below. Then update our
443 * state with this packet's header.
445 deltaA
= ntohs(th
->check
);
446 memcpy(&cs
->cs_ip
,ip
,20);
447 memcpy(&cs
->cs_tcp
,th
,20);
448 /* We want to use the original packet as our compressed packet.
449 * (cp - new_seq) is the number of bytes we need for compressed
450 * sequence numbers. In addition we need one byte for the change
451 * mask, one for the connection id and two for the tcp checksum.
452 * So, (cp - new_seq) + 4 bytes of header are needed.
454 deltaS
= cp
- new_seq
;
455 if(compress_cid
== 0 || comp
->xmit_current
!= cs
->cs_this
){
458 *cp
++ = changes
| NEW_C
;
460 comp
->xmit_current
= cs
->cs_this
;
466 cp
= put16(cp
,(short)deltaA
); /* Write TCP checksum */
467 /* deltaS is now the size of the change section of the compressed header */
468 memcpy(cp
,new_seq
,deltaS
); /* Write list of deltas */
469 memcpy(cp
+deltaS
,icp
+hlen
,isize
-hlen
);
470 comp
->sls_o_compressed
++;
471 ocp
[0] |= SL_TYPE_COMPRESSED_TCP
;
472 return isize
- hlen
+ deltaS
+ (cp
- ocp
);
474 /* Update connection state cs & send uncompressed packet (i.e.,
475 * a regular ip/tcp packet but with the 'conversation id' we hope
476 * to use on future compressed packets in the protocol field).
479 memcpy(&cs
->cs_ip
,ip
,20);
480 memcpy(&cs
->cs_tcp
,th
,20);
482 memcpy(cs
->cs_ipopt
, ip
+1, ((ip
->ihl
) - 5) * 4);
484 memcpy(cs
->cs_tcpopt
, th
+1, ((th
->doff
) - 5) * 4);
485 comp
->xmit_current
= cs
->cs_this
;
486 comp
->sls_o_uncompressed
++;
487 memcpy(ocp
, icp
, isize
);
489 ocp
[9] = cs
->cs_this
;
490 ocp
[0] |= SL_TYPE_UNCOMPRESSED_TCP
;
496 slhc_uncompress(struct slcompress
*comp
, unsigned char *icp
, int isize
)
498 register int changes
;
500 register struct tcphdr
*thp
;
501 register struct iphdr
*ip
;
502 register struct cstate
*cs
;
504 unsigned char *cp
= icp
;
506 /* We've got a compressed packet; read the change byte */
507 comp
->sls_i_compressed
++;
514 /* Make sure the state index is in range, then grab the state.
515 * If we have a good state index, clear the 'discard' flag.
517 x
= *cp
++; /* Read conn index */
518 if(x
< 0 || x
> comp
->rslot_limit
)
521 comp
->flags
&=~ SLF_TOSS
;
522 comp
->recv_current
= x
;
524 /* this packet has an implicit state index. If we've
525 * had a line error since the last time we got an
526 * explicit state index, we have to toss the packet. */
527 if(comp
->flags
& SLF_TOSS
){
528 comp
->sls_i_tossed
++;
532 cs
= &comp
->rstate
[comp
->recv_current
];
536 if((x
= pull16(&cp
)) == -1) { /* Read the TCP checksum */
539 thp
->check
= htons(x
);
541 thp
->psh
= (changes
& TCP_PUSH_BIT
) ? 1 : 0;
543 * we can use the same number for the length of the saved header and
544 * the current one, because the packet wouldn't have been sent
545 * as compressed unless the options were the same as the previous one
548 hdrlen
= ip
->ihl
* 4 + thp
->doff
* 4;
550 switch(changes
& SPECIALS_MASK
){
551 case SPECIAL_I
: /* Echoed terminal traffic */
554 i
= ntohs(ip
->tot_len
) - hdrlen
;
555 thp
->ack_seq
= htonl( ntohl(thp
->ack_seq
) + i
);
556 thp
->seq
= htonl( ntohl(thp
->seq
) + i
);
560 case SPECIAL_D
: /* Unidirectional data */
561 thp
->seq
= htonl( ntohl(thp
->seq
) +
562 ntohs(ip
->tot_len
) - hdrlen
);
568 if((x
= decode(&cp
)) == -1) {
571 thp
->urg_ptr
= htons(x
);
575 if((x
= decode(&cp
)) == -1) {
578 thp
->window
= htons( ntohs(thp
->window
) + x
);
581 if((x
= decode(&cp
)) == -1) {
584 thp
->ack_seq
= htonl( ntohl(thp
->ack_seq
) + x
);
587 if((x
= decode(&cp
)) == -1) {
590 thp
->seq
= htonl( ntohl(thp
->seq
) + x
);
595 if((x
= decode(&cp
)) == -1) {
598 ip
->id
= htons (ntohs (ip
->id
) + x
);
600 ip
->id
= htons (ntohs (ip
->id
) + 1);
603 * At this point, cp points to the first byte of data in the
604 * packet. Put the reconstructed TCP and IP headers back on the
605 * packet. Recalculate IP checksum (but not TCP checksum).
608 len
= isize
- (cp
- icp
);
612 ip
->tot_len
= htons(len
);
615 memmove(icp
+ hdrlen
, cp
, len
- hdrlen
);
622 memcpy(cp
, cs
->cs_ipopt
, (ip
->ihl
- 5) * 4);
623 cp
+= (ip
->ihl
- 5) * 4;
626 put_unaligned(ip_fast_csum(icp
, ip
->ihl
),
627 &((struct iphdr
*)icp
)->check
);
633 memcpy(cp
, cs
->cs_tcpopt
, ((thp
->doff
) - 5) * 4);
634 cp
+= ((thp
->doff
) - 5) * 4;
640 return slhc_toss( comp
);
645 slhc_remember(struct slcompress
*comp
, unsigned char *icp
, int isize
)
647 register struct cstate
*cs
;
653 /* The packet is shorter than a legal IP header */
655 return slhc_toss( comp
);
657 /* Peek at the IP header's IHL field to find its length */
660 /* The IP header length field is too small */
662 return slhc_toss( comp
);
665 icp
[9] = IPPROTO_TCP
;
667 if (ip_fast_csum(icp
, ihl
)) {
668 /* Bad IP header checksum; discard */
669 comp
->sls_i_badcheck
++;
670 return slhc_toss( comp
);
672 if(index
> comp
->rslot_limit
) {
674 return slhc_toss(comp
);
677 /* Update local state */
678 cs
= &comp
->rstate
[comp
->recv_current
= index
];
679 comp
->flags
&=~ SLF_TOSS
;
680 memcpy(&cs
->cs_ip
,icp
,20);
681 memcpy(&cs
->cs_tcp
,icp
+ ihl
*4,20);
683 memcpy(cs
->cs_ipopt
, icp
+ sizeof(struct iphdr
), (ihl
- 5) * 4);
684 if (cs
->cs_tcp
.doff
> 5)
685 memcpy(cs
->cs_tcpopt
, icp
+ ihl
*4 + sizeof(struct tcphdr
), (cs
->cs_tcp
.doff
- 5) * 4);
686 cs
->cs_hsize
= ihl
*2 + cs
->cs_tcp
.doff
*2;
687 /* Put headers back on packet
688 * Neither header checksum is recalculated
690 comp
->sls_i_uncompressed
++;
696 slhc_toss(struct slcompress
*comp
)
698 if ( comp
== NULLSLCOMPR
)
701 comp
->flags
|= SLF_TOSS
;
706 void slhc_i_status(struct slcompress
*comp
)
708 if (comp
!= NULLSLCOMPR
) {
709 printk("\t%d Cmp, %d Uncmp, %d Bad, %d Tossed\n",
710 comp
->sls_i_compressed
,
711 comp
->sls_i_uncompressed
,
718 void slhc_o_status(struct slcompress
*comp
)
720 if (comp
!= NULLSLCOMPR
) {
721 printk("\t%d Cmp, %d Uncmp, %d AsIs, %d NotTCP\n",
722 comp
->sls_o_compressed
,
723 comp
->sls_o_uncompressed
,
726 printk("\t%10d Searches, %10d Misses\n",
727 comp
->sls_o_searches
,
732 /* Should this be surrounded with "#ifdef CONFIG_MODULES" ? */
733 /* VJ header compression */
734 EXPORT_SYMBOL(slhc_init
);
735 EXPORT_SYMBOL(slhc_free
);
736 EXPORT_SYMBOL(slhc_remember
);
737 EXPORT_SYMBOL(slhc_compress
);
738 EXPORT_SYMBOL(slhc_uncompress
);
739 EXPORT_SYMBOL(slhc_toss
);
743 int init_module(void)
745 printk(KERN_INFO
"CSLIP: code copyright 1989 Regents of the University of California\n");
749 void cleanup_module(void)
755 int __init
slhc_install(void)
761 #else /* CONFIG_INET */
765 slhc_toss(struct slcompress
*comp
)
767 printk(KERN_DEBUG
"Called IP function on non IP-system: slhc_toss");
771 slhc_uncompress(struct slcompress
*comp
, unsigned char *icp
, int isize
)
773 printk(KERN_DEBUG
"Called IP function on non IP-system: slhc_uncompress");
777 slhc_compress(struct slcompress
*comp
, unsigned char *icp
, int isize
,
778 unsigned char *ocp
, unsigned char **cpp
, int compress_cid
)
780 printk(KERN_DEBUG
"Called IP function on non IP-system: slhc_compress");
785 slhc_remember(struct slcompress
*comp
, unsigned char *icp
, int isize
)
787 printk(KERN_DEBUG
"Called IP function on non IP-system: slhc_remember");
792 slhc_free(struct slcompress
*comp
)
794 printk(KERN_DEBUG
"Called IP function on non IP-system: slhc_free");
798 slhc_init(int rslots
, int tslots
)
800 printk(KERN_DEBUG
"Called IP function on non IP-system: slhc_init");
803 EXPORT_SYMBOL(slhc_init
);
804 EXPORT_SYMBOL(slhc_free
);
805 EXPORT_SYMBOL(slhc_remember
);
806 EXPORT_SYMBOL(slhc_compress
);
807 EXPORT_SYMBOL(slhc_uncompress
);
808 EXPORT_SYMBOL(slhc_toss
);
810 #endif /* CONFIG_INET */