1 /*
2 * Copyright (c) 2000 by Sun Microsystems, Inc.
3 * All rights reserved.
4 *
5 * Routines to compress and uncompess tcp packets (for transmission
6 * over low speed serial lines.
7 *
8 * Copyright (c) 1989 Regents of the University of California.
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms are permitted
12 * provided that the above copyright notice and this paragraph are
13 * duplicated in all such forms and that any documentation,
14 * advertising materials, and other materials related to such
15 * distribution and use acknowledge that the software was developed
16 * by the University of California, Berkeley. The name of the
17 * University may not be used to endorse or promote products derived
18 * from this software without specific prior written permission.
19 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
20 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
21 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
22 *
23 * Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
24 * - Initial distribution.
25 *
26 * Modified June 1993 by Paul Mackerras, paulus@cs.anu.edu.au,
27 * so that the entire packet being decompressed doesn't have
28 * to be in contiguous memory (just the compressed header).
29 */
30
31 /*
32 * This version is used under STREAMS in Solaris 2
33 *
34 * $Id: vjcompress.c,v 1.10 1999/09/15 23:49:06 masputra Exp $
35 */
36
37 #include <sys/types.h>
38 #include <sys/param.h>
39 #include <sys/byteorder.h> /* for ntohl, etc. */
40 #include <sys/systm.h>
41 #include <sys/sysmacros.h>
42
43 #include <netinet/in.h>
44 #include <netinet/in_systm.h>
45 #include <netinet/ip.h>
46 #include <netinet/tcp.h>
47
48 #include <net/ppp_defs.h>
49 #include <net/vjcompress.h>
50
51 #pragma ident "%Z%%M% %I% %E% SMI"
52
53 #ifndef VJ_NO_STATS
54 #define INCR(counter) ++comp->stats.counter
55 #else
56 #define INCR(counter)
57 #endif
58
59 #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (unsigned int)(n))
60
61 #undef BCOPY
62 #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (unsigned int)(n))
63
64 /*
65 * I'd like to use offsetof(struct ip,ip_hl) and offsetof(struct
66 * tcp,th_off), but these are bitfields.
67 */
68 #define getip_hl(bp) (((uchar_t *)bp)[0] & 0x0F)
69 #define getth_off(bp) (((uchar_t *)bp)[12] >> 4)
70 #define getip_p(bp) (((uchar_t *)bp)[offsetof(struct ip, ip_p)])
71 #define setip_p(bp, v) (((uchar_t *)bp)[offsetof(struct ip, ip_p)] = (v))
72
73 /*
74 * vj_compress_init()
75 */
76 void
vj_compress_init(struct vjcompress * comp,int max_state)77 vj_compress_init(struct vjcompress *comp, int max_state)
78 {
79 register uint_t i;
80 register struct cstate *tstate = comp->tstate;
81
82 if (max_state == -1) {
83 max_state = MAX_STATES - 1;
84 }
85
86 bzero((char *)comp, sizeof (*comp));
87
88 for (i = max_state; i > 0; --i) {
89 tstate[i].cs_id = i & 0xff;
90 tstate[i].cs_next = &tstate[i - 1];
91 }
92
93 tstate[0].cs_next = &tstate[max_state];
94 tstate[0].cs_id = 0;
95
96 comp->last_cs = &tstate[0];
97 comp->last_recv = 255;
98 comp->last_xmit = 255;
99 comp->flags = VJF_TOSS;
100 }
101
102 /*
103 * ENCODE encodes a number that is known to be non-zero. ENCODEZ
104 * checks for zero (since zero has to be encoded in the long, 3 byte
105 * form).
106 */
107 #define ENCODE(n) { \
108 if ((ushort_t)(n) >= 256) { \
109 *cp++ = 0; \
110 cp[1] = (n) & 0xff; \
111 cp[0] = ((n) >> 8) & 0xff; \
112 cp += 2; \
113 } else { \
114 *cp++ = (n) & 0xff; \
115 } \
116 }
117 #define ENCODEZ(n) { \
118 if ((ushort_t)(n) >= 256 || (ushort_t)(n) == 0) { \
119 *cp++ = 0; \
120 cp[1] = (n) & 0xff; \
121 cp[0] = ((n) >> 8) & 0xff; \
122 cp += 2; \
123 } else { \
124 *cp++ = (n) & 0xff; \
125 } \
126 }
127
128 #define DECODEL(f) { \
129 if (*cp == 0) { \
130 uint32_t tmp = ntohl(f) + ((cp[1] << 8) | cp[2]); \
131 (f) = htonl(tmp); \
132 cp += 3; \
133 } else { \
134 uint32_t tmp = ntohl(f) + (uint32_t)*cp++; \
135 (f) = htonl(tmp); \
136 } \
137 }
138
139 #define DECODES(f) { \
140 if (*cp == 0) { \
141 ushort_t tmp = ntohs(f) + ((cp[1] << 8) | cp[2]); \
142 (f) = htons(tmp); \
143 cp += 3; \
144 } else { \
145 ushort_t tmp = ntohs(f) + (uint32_t)*cp++; \
146 (f) = htons(tmp); \
147 } \
148 }
149
150 #define DECODEU(f) { \
151 if (*cp == 0) { \
152 (f) = htons((cp[1] << 8) | cp[2]); \
153 cp += 3; \
154 } else { \
155 (f) = htons((uint32_t)*cp++); \
156 } \
157 }
158
159 uint_t
vj_compress_tcp(register struct ip * ip,uint_t mlen,struct vjcompress * comp,int compress_cid,uchar_t ** vjhdrp)160 vj_compress_tcp(register struct ip *ip, uint_t mlen, struct vjcompress *comp,
161 int compress_cid, uchar_t **vjhdrp)
162 {
163 register struct cstate *cs = comp->last_cs->cs_next;
164 register uint_t hlen = getip_hl(ip);
165 register struct tcphdr *oth;
166 register struct tcphdr *th;
167 register uint_t deltaS;
168 register uint_t deltaA;
169 register uint_t changes = 0;
170 uchar_t new_seq[16];
171 register uchar_t *cp = new_seq;
172 register uint_t thlen;
173
174 /*
175 * Bail if this is an IP fragment or if the TCP packet isn't
176 * `compressible' (i.e., ACK isn't set or some other control bit is
177 * set). (We assume that the caller has already made sure the
178 * packet is IP proto TCP)
179 */
180 if ((ip->ip_off & htons(0x3fff)) || mlen < 40) {
181 return (TYPE_IP);
182 }
183
184 th = (struct tcphdr *)&((int *)ip)[hlen];
185
186 if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK) {
187 return (TYPE_IP);
188 }
189
190 thlen = (hlen + getth_off(th)) << 2;
191 if (thlen > mlen) {
192 return (TYPE_IP);
193 }
194
195 /*
196 * Packet is compressible -- we're going to send either a
197 * COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way we need
198 * to locate (or create) the connection state. Special case the
199 * most recently used connection since it's most likely to be used
200 * again & we don't have to do any reordering if it's used.
201 */
202 INCR(vjs_packets);
203
204 if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
205 ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
206 *(int *)th != ((int *)&cs->cs_ip)[getip_hl(&cs->cs_ip)]) {
207
208 /*
209 * Wasn't the first -- search for it.
210 *
211 * States are kept in a circularly linked list with
212 * last_cs pointing to the end of the list. The
213 * list is kept in lru order by moving a state to the
214 * head of the list whenever it is referenced. Since
215 * the list is short and, empirically, the connection
216 * we want is almost always near the front, we locate
217 * states via linear search. If we don't find a state
218 * for the datagram, the oldest state is (re-)used.
219 */
220 register struct cstate *lcs;
221 register struct cstate *lastcs = comp->last_cs;
222
223 do {
224 lcs = cs; cs = cs->cs_next;
225
226 INCR(vjs_searches);
227
228 if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr &&
229 ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr &&
230 *(int *)th == ((int *)
231 &cs->cs_ip)[getip_hl(&cs->cs_ip)]) {
232
233 goto found;
234 }
235
236 } while (cs != lastcs);
237
238 /*
239 * Didn't find it -- re-use oldest cstate. Send an
240 * uncompressed packet that tells the other side what
241 * connection number we're using for this conversation.
242 * Note that since the state list is circular, the oldest
243 * state points to the newest and we only need to set
244 * last_cs to update the lru linkage.
245 */
246 INCR(vjs_misses);
247
248 comp->last_cs = lcs;
249
250 goto uncompressed;
251
252 found:
253 /*
254 * Found it -- move to the front on the connection list.
255 */
256 if (cs == lastcs) {
257 comp->last_cs = lcs;
258 } else {
259 lcs->cs_next = cs->cs_next;
260 cs->cs_next = lastcs->cs_next;
261 lastcs->cs_next = cs;
262 }
263 }
264
265 /*
266 * Make sure that only what we expect to change changed. The first
267 * line of the `if' checks the IP protocol version, header length &
268 * type of service. The 2nd line checks the "Don't fragment" bit.
269 * The 3rd line checks the time-to-live and protocol (the protocol
270 * check is unnecessary but costless). The 4th line checks the TCP
271 * header length. The 5th line checks IP options, if any. The 6th
272 * line checks TCP options, if any. If any of these things are
273 * different between the previous & current datagram, we send the
274 * current datagram `uncompressed'.
275 */
276 oth = (struct tcphdr *)&((int *)&cs->cs_ip)[hlen];
277
278 /* Used to check for IP options. */
279 deltaS = hlen;
280
281 if (((ushort_t *)ip)[0] != ((ushort_t *)&cs->cs_ip)[0] ||
282 ((ushort_t *)ip)[3] != ((ushort_t *)&cs->cs_ip)[3] ||
283 ((ushort_t *)ip)[4] != ((ushort_t *)&cs->cs_ip)[4] ||
284 getth_off(th) != getth_off(oth) ||
285 (deltaS > 5 &&
286 BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
287 (getth_off(th) > 5 &&
288 BCMP(th + 1, oth + 1, (getth_off(th) - 5) << 2))) {
289
290 goto uncompressed;
291 }
292
293 /*
294 * Figure out which of the changing fields changed. The
295 * receiver expects changes in the order: urgent, window,
296 * ack, seq (the order minimizes the number of temporaries
297 * needed in this section of code).
298 */
299 if (th->th_flags & TH_URG) {
300
301 deltaS = ntohs(th->th_urp);
302
303 ENCODEZ(deltaS);
304
305 changes |= NEW_U;
306
307 } else if (th->th_urp != oth->th_urp) {
308
309 /*
310 * argh! URG not set but urp changed -- a sensible
311 * implementation should never do this but RFC793
312 * doesn't prohibit the change so we have to deal
313 * with it
314 */
315 goto uncompressed;
316 }
317
318 if ((deltaS = (ushort_t)(ntohs(th->th_win) - ntohs(oth->th_win))) > 0) {
319 ENCODE(deltaS);
320
321 changes |= NEW_W;
322 }
323
324 if ((deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) > 0) {
325 if (deltaA > 0xffff) {
326 goto uncompressed;
327 }
328
329 ENCODE(deltaA);
330
331 changes |= NEW_A;
332 }
333
334 if ((deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) > 0) {
335 if (deltaS > 0xffff) {
336 goto uncompressed;
337 }
338
339 ENCODE(deltaS);
340
341 changes |= NEW_S;
342 }
343
344 switch (changes) {
345
346 case 0:
347 /*
348 * Nothing changed. If this packet contains data and the
349 * last one didn't, this is probably a data packet following
350 * an ack (normal on an interactive connection) and we send
351 * it compressed. Otherwise it's probably a retransmit,
352 * retransmitted ack or window probe. Send it uncompressed
353 * in case the other side missed the compressed version.
354 */
355 if (ip->ip_len != cs->cs_ip.ip_len &&
356 ntohs(cs->cs_ip.ip_len) == thlen) {
357 break;
358 }
359
360 /* (otherwise fall through) */
361 /* FALLTHRU */
362
363 case SPECIAL_I:
364 case SPECIAL_D:
365
366 /*
367 * actual changes match one of our special case encodings --
368 * send packet uncompressed.
369 */
370 goto uncompressed;
371
372 case NEW_S|NEW_A:
373
374 if (deltaS == deltaA &&
375 deltaS == ntohs(cs->cs_ip.ip_len) - thlen) {
376
377 /*
378 * special case for echoed terminal traffic
379 */
380 changes = SPECIAL_I;
381 cp = new_seq;
382 }
383
384 break;
385
386 case NEW_S:
387
388 if (deltaS == ntohs(cs->cs_ip.ip_len) - thlen) {
389
390 /*
391 * special case for data xfer
392 */
393 changes = SPECIAL_D;
394 cp = new_seq;
395 }
396
397 break;
398 }
399
400 deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
401 if (deltaS != 1) {
402 ENCODEZ(deltaS);
403
404 changes |= NEW_I;
405 }
406
407 if (th->th_flags & TH_PUSH) {
408 changes |= TCP_PUSH_BIT;
409 }
410
411 /*
412 * Grab the cksum before we overwrite it below. Then update our
413 * state with this packet's header.
414 */
415 deltaA = ntohs(th->th_sum);
416
417 BCOPY(ip, &cs->cs_ip, thlen);
418
419 /*
420 * We want to use the original packet as our compressed packet.
421 * (cp - new_seq) is the number of bytes we need for compressed
422 * sequence numbers. In addition we need one byte for the change
423 * mask, one for the connection id and two for the tcp checksum.
424 * So, (cp - new_seq) + 4 bytes of header are needed. thlen is how
425 * many bytes of the original packet to toss so subtract the two to
426 * get the new packet size.
427 */
428 deltaS = cp - new_seq;
429
430 cp = (uchar_t *)ip;
431
432 if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {
433 comp->last_xmit = cs->cs_id;
434
435 thlen -= deltaS + 4;
436
437 *vjhdrp = (cp += thlen);
438
439 *cp++ = changes | NEW_C;
440 *cp++ = cs->cs_id;
441 } else {
442 thlen -= deltaS + 3;
443
444 *vjhdrp = (cp += thlen);
445
446 *cp++ = changes & 0xff;
447 }
448
449 *cp++ = (deltaA >> 8) & 0xff;
450 *cp++ = deltaA & 0xff;
451
452 BCOPY(new_seq, cp, deltaS);
453
454 INCR(vjs_compressed);
455
456 return (TYPE_COMPRESSED_TCP);
457
458 /*
459 * Update connection state cs & send uncompressed packet (that is,
460 * a regular ip/tcp packet but with the 'conversation id' we hope
461 * to use on future compressed packets in the protocol field).
462 */
463 uncompressed:
464
465 BCOPY(ip, &cs->cs_ip, thlen);
466
467 ip->ip_p = cs->cs_id;
468 comp->last_xmit = cs->cs_id;
469
470 return (TYPE_UNCOMPRESSED_TCP);
471 }
472
473 /*
474 * vj_uncompress_err()
475 *
476 * Called when we may have missed a packet.
477 */
478 void
vj_uncompress_err(struct vjcompress * comp)479 vj_uncompress_err(struct vjcompress *comp)
480 {
481 comp->flags |= VJF_TOSS;
482
483 INCR(vjs_errorin);
484 }
485
486 /*
487 * vj_uncompress_uncomp()
488 *
489 * "Uncompress" a packet of type TYPE_UNCOMPRESSED_TCP.
490 */
491 int
vj_uncompress_uncomp(uchar_t * buf,int buflen,struct vjcompress * comp)492 vj_uncompress_uncomp(uchar_t *buf, int buflen, struct vjcompress *comp)
493 {
494 register uint_t hlen;
495 register struct cstate *cs;
496
497 hlen = getip_hl(buf) << 2;
498
499 if (getip_p(buf) >= MAX_STATES ||
500 hlen + sizeof (struct tcphdr) > buflen ||
501 (hlen += getth_off(buf+hlen) << 2) > buflen || hlen > MAX_HDR) {
502
503 comp->flags |= VJF_TOSS;
504
505 INCR(vjs_errorin);
506
507 return (0);
508 }
509
510 cs = &comp->rstate[comp->last_recv = getip_p(buf)];
511 comp->flags &= ~VJF_TOSS;
512 setip_p(buf, IPPROTO_TCP);
513
514 BCOPY(buf, &cs->cs_ip, hlen);
515
516 cs->cs_hlen = hlen & 0xff;
517
518 INCR(vjs_uncompressedin);
519
520 return (1);
521 }
522
523 /*
524 * vj_uncompress_tcp()
525 *
526 * Uncompress a packet of type TYPE_COMPRESSED_TCP.
527 * The packet starts at buf and is of total length total_len.
528 * The first buflen bytes are at buf; this must include the entire
529 * compressed TCP/IP header. This procedure returns the length
530 * of the VJ header, with a pointer to the uncompressed IP header
531 * in *hdrp and its length in *hlenp.
532 */
533 int
vj_uncompress_tcp(uchar_t * buf,int buflen,int total_len,struct vjcompress * comp,uchar_t ** hdrp,uint_t * hlenp)534 vj_uncompress_tcp(uchar_t *buf, int buflen, int total_len,
535 struct vjcompress *comp, uchar_t **hdrp, uint_t *hlenp)
536 {
537 register uchar_t *cp;
538 register uint_t hlen;
539 register uint_t changes;
540 register struct tcphdr *th;
541 register struct cstate *cs;
542 register ushort_t *bp;
543 register uint_t vjlen;
544 register uint32_t tmp;
545
546 INCR(vjs_compressedin);
547
548 cp = buf;
549 changes = *cp++;
550
551 if (changes & NEW_C) {
552 /*
553 * Make sure the state index is in range, then grab the state.
554 * If we have a good state index, clear the 'discard' flag.
555 */
556 if (*cp >= MAX_STATES) {
557 goto bad;
558 }
559
560 comp->flags &= ~VJF_TOSS;
561 comp->last_recv = *cp++;
562 } else {
563 /*
564 * this packet has an implicit state index. If we've
565 * had a line error since the last time we got an
566 * explicit state index, we have to toss the packet
567 */
568 if (comp->flags & VJF_TOSS) {
569 INCR(vjs_tossed);
570 return (-1);
571 }
572 }
573
574 cs = &comp->rstate[comp->last_recv];
575 hlen = getip_hl(&cs->cs_ip) << 2;
576
577 th = (struct tcphdr *)((uint32_t *)&cs->cs_ip+hlen/sizeof (uint32_t));
578 th->th_sum = htons((*cp << 8) | cp[1]);
579
580 cp += 2;
581
582 if (changes & TCP_PUSH_BIT) {
583 th->th_flags |= TH_PUSH;
584 } else {
585 th->th_flags &= ~TH_PUSH;
586 }
587
588 switch (changes & SPECIALS_MASK) {
589
590 case SPECIAL_I:
591
592 {
593
594 register uint32_t i;
595
596 i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
597
598 tmp = ntohl(th->th_ack) + i;
599 th->th_ack = htonl(tmp);
600
601 tmp = ntohl(th->th_seq) + i;
602 th->th_seq = htonl(tmp);
603
604 }
605
606 break;
607
608 case SPECIAL_D:
609
610 tmp = ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
611 th->th_seq = htonl(tmp);
612
613 break;
614
615 default:
616
617 if (changes & NEW_U) {
618 th->th_flags |= TH_URG;
619 DECODEU(th->th_urp);
620 } else {
621 th->th_flags &= ~TH_URG;
622 }
623
624 if (changes & NEW_W) {
625 DECODES(th->th_win);
626 }
627
628 if (changes & NEW_A) {
629 DECODEL(th->th_ack);
630 }
631
632 if (changes & NEW_S) {
633 DECODEL(th->th_seq);
634 }
635
636 break;
637 }
638
639 if (changes & NEW_I) {
640 DECODES(cs->cs_ip.ip_id);
641 } else {
642 cs->cs_ip.ip_id = ntohs(cs->cs_ip.ip_id) + 1;
643 cs->cs_ip.ip_id = htons(cs->cs_ip.ip_id);
644 }
645
646 /*
647 * At this point, cp points to the first byte of data in the
648 * packet. Fill in the IP total length and update the IP
649 * header checksum.
650 */
651 vjlen = cp - buf;
652 buflen -= vjlen;
653 if (buflen < 0) {
654 /*
655 * we must have dropped some characters (crc should detect
656 * this but the old slip framing won't)
657 */
658 goto bad;
659 }
660
661 total_len += cs->cs_hlen - vjlen;
662 cs->cs_ip.ip_len = htons(total_len);
663
664 /*
665 * recompute the ip header checksum
666 */
667 bp = (ushort_t *)&cs->cs_ip;
668 cs->cs_ip.ip_sum = 0;
669
670 for (changes = 0; hlen > 0; hlen -= 2) {
671 changes += *bp++;
672 }
673
674 changes = (changes & 0xffff) + (changes >> 16);
675 changes = (changes & 0xffff) + (changes >> 16);
676 cs->cs_ip.ip_sum = ~ changes;
677
678 *hdrp = (uchar_t *)&cs->cs_ip;
679 *hlenp = cs->cs_hlen;
680
681 return (vjlen);
682
683 bad:
684
685 comp->flags |= VJF_TOSS;
686
687 INCR(vjs_errorin);
688
689 return (-1);
690 }
691