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