]> git.saurik.com Git - apple/xnu.git/blob - bsd/net/slcompress.c
xnu-344.49.tar.gz
[apple/xnu.git] / bsd / net / slcompress.c
1 /*
2 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_LICENSE_HEADER_START@
5 *
6 * Copyright (c) 1999-2003 Apple Computer, Inc. All Rights Reserved.
7 *
8 * This file contains Original Code and/or Modifications of Original Code
9 * as defined in and that are subject to the Apple Public Source License
10 * Version 2.0 (the 'License'). You may not use this file except in
11 * compliance with the License. Please obtain a copy of the License at
12 * http://www.opensource.apple.com/apsl/ and read it before using this
13 * file.
14 *
15 * The Original Code and all software distributed under the License are
16 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
17 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
18 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
20 * Please see the License for the specific language governing rights and
21 * limitations under the License.
22 *
23 * @APPLE_LICENSE_HEADER_END@
24 */
25 /*-
26 * Copyright (c) 1989, 1993, 1994
27 * The Regents of the University of California. All rights reserved.
28 *
29 * Redistribution and use in source and binary forms, with or without
30 * modification, are permitted provided that the following conditions
31 * are met:
32 * 1. Redistributions of source code must retain the above copyright
33 * notice, this list of conditions and the following disclaimer.
34 * 2. Redistributions in binary form must reproduce the above copyright
35 * notice, this list of conditions and the following disclaimer in the
36 * documentation and/or other materials provided with the distribution.
37 * 3. All advertising materials mentioning features or use of this software
38 * must display the following acknowledgement:
39 * This product includes software developed by the University of
40 * California, Berkeley and its contributors.
41 * 4. Neither the name of the University nor the names of its contributors
42 * may be used to endorse or promote products derived from this software
43 * without specific prior written permission.
44 *
45 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
46 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
47 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
48 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
49 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
50 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
51 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
52 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
53 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
54 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
55 * SUCH DAMAGE.
56 *
57 * @(#)slcompress.c 8.2 (Berkeley) 4/16/94
58 * $FreeBSD: src/sys/net/slcompress.c,v 1.16 1999/12/29 04:38:37 peter Exp $
59 */
60
61 /*
62 * Routines to compress and uncompess tcp packets (for transmission
63 * over low speed serial lines.
64 *
65 * Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989:
66 * - Initial distribution.
67 *
68 */
69
70 #include <sys/param.h>
71 #include <sys/mbuf.h>
72 #include <sys/systm.h>
73
74 #include <netinet/in.h>
75 #include <netinet/in_systm.h>
76 #include <netinet/ip.h>
77 #include <netinet/tcp.h>
78
79 #include <net/slcompress.h>
80
81 #ifndef SL_NO_STATS
82 #define INCR(counter) ++comp->counter;
83 #else
84 #define INCR(counter)
85 #endif
86
87 #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n))
88 #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n))
89 #ifndef KERNEL
90 #define ovbcopy bcopy
91 #endif
92
93 void
94 sl_compress_init(comp, max_state)
95 struct slcompress *comp;
96 int max_state;
97 {
98 register u_int i;
99 register struct cstate *tstate = comp->tstate;
100
101 if (max_state == -1) {
102 max_state = MAX_STATES - 1;
103 bzero((char *)comp, sizeof(*comp));
104 } else {
105 /* Don't reset statistics */
106 bzero((char *)comp->tstate, sizeof(comp->tstate));
107 bzero((char *)comp->rstate, sizeof(comp->rstate));
108 }
109 for (i = max_state; i > 0; --i) {
110 tstate[i].cs_id = i;
111 tstate[i].cs_next = &tstate[i - 1];
112 }
113 tstate[0].cs_next = &tstate[max_state];
114 tstate[0].cs_id = 0;
115 comp->last_cs = &tstate[0];
116 comp->last_recv = 255;
117 comp->last_xmit = 255;
118 comp->flags = SLF_TOSS;
119 }
120
121
122 /* ENCODE encodes a number that is known to be non-zero. ENCODEZ
123 * checks for zero (since zero has to be encoded in the long, 3 byte
124 * form).
125 */
126 #define ENCODE(n) { \
127 if ((u_int16_t)(n) >= 256) { \
128 *cp++ = 0; \
129 cp[1] = (n); \
130 cp[0] = (n) >> 8; \
131 cp += 2; \
132 } else { \
133 *cp++ = (n); \
134 } \
135 }
136 #define ENCODEZ(n) { \
137 if ((u_int16_t)(n) >= 256 || (u_int16_t)(n) == 0) { \
138 *cp++ = 0; \
139 cp[1] = (n); \
140 cp[0] = (n) >> 8; \
141 cp += 2; \
142 } else { \
143 *cp++ = (n); \
144 } \
145 }
146
147 #define DECODEL(f) { \
148 if (*cp == 0) {\
149 (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
150 cp += 3; \
151 } else { \
152 (f) = htonl(ntohl(f) + (u_int32_t)*cp++); \
153 } \
154 }
155
156 #define DECODES(f) { \
157 if (*cp == 0) {\
158 (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
159 cp += 3; \
160 } else { \
161 (f) = htons(ntohs(f) + (u_int32_t)*cp++); \
162 } \
163 }
164
165 #define DECODEU(f) { \
166 if (*cp == 0) {\
167 (f) = htons((cp[1] << 8) | cp[2]); \
168 cp += 3; \
169 } else { \
170 (f) = htons((u_int32_t)*cp++); \
171 } \
172 }
173
174 /*
175 * Attempt to compress an outgoing TCP packet and return the type of
176 * the result. The caller must have already verified that the protocol
177 * is TCP. The first mbuf must contain the complete IP and TCP headers,
178 * and "ip" must be == mtod(m, struct ip *). "comp" supplies the
179 * compression state, and "compress_cid" tells us whether it is OK
180 * to leave out the CID field when feasible.
181 *
182 * The caller is responsible for adjusting m->m_pkthdr.len upon return,
183 * if m is an M_PKTHDR mbuf.
184 */
185 u_int
186 sl_compress_tcp(m, ip, comp, compress_cid)
187 struct mbuf *m;
188 register struct ip *ip;
189 struct slcompress *comp;
190 int compress_cid;
191 {
192 register struct cstate *cs = comp->last_cs->cs_next;
193 register u_int hlen = ip->ip_hl;
194 register struct tcphdr *oth;
195 register struct tcphdr *th;
196 register u_int deltaS, deltaA;
197 register u_int changes = 0;
198 u_char new_seq[16];
199 register u_char *cp = new_seq;
200
201 /*
202 * Bail if this is an IP fragment or if the TCP packet isn't
203 * `compressible' (i.e., ACK isn't set or some other control bit is
204 * set). (We assume that the caller has already made sure the
205 * packet is IP proto TCP).
206 */
207 if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40)
208 return (TYPE_IP);
209
210 th = (struct tcphdr *)&((int32_t *)ip)[hlen];
211 if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK)
212 return (TYPE_IP);
213 /*
214 * Packet is compressible -- we're going to send either a
215 * COMPRESSED_TCP or UNCOMPRESSED_TCP packet. Either way we need
216 * to locate (or create) the connection state. Special case the
217 * most recently used connection since it's most likely to be used
218 * again & we don't have to do any reordering if it's used.
219 */
220 INCR(sls_packets)
221 if (ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr ||
222 ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr ||
223 *(int32_t *)th != ((int32_t *)&cs->cs_ip)[cs->cs_ip.ip_hl]) {
224 /*
225 * Wasn't the first -- search for it.
226 *
227 * States are kept in a circularly linked list with
228 * last_cs pointing to the end of the list. The
229 * list is kept in lru order by moving a state to the
230 * head of the list whenever it is referenced. Since
231 * the list is short and, empirically, the connection
232 * we want is almost always near the front, we locate
233 * states via linear search. If we don't find a state
234 * for the datagram, the oldest state is (re-)used.
235 */
236 register struct cstate *lcs;
237 register struct cstate *lastcs = comp->last_cs;
238
239 do {
240 lcs = cs; cs = cs->cs_next;
241 INCR(sls_searches)
242 if (ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr
243 && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr
244 && *(int32_t *)th ==
245 ((int32_t *)&cs->cs_ip)[cs->cs_ip.ip_hl])
246 goto found;
247 } while (cs != lastcs);
248
249 /*
250 * Didn't find it -- re-use oldest cstate. Send an
251 * uncompressed packet that tells the other side what
252 * connection number we're using for this conversation.
253 * Note that since the state list is circular, the oldest
254 * state points to the newest and we only need to set
255 * last_cs to update the lru linkage.
256 */
257 INCR(sls_misses)
258 comp->last_cs = lcs;
259 hlen += th->th_off;
260 hlen <<= 2;
261 if (hlen > m->m_len)
262 return TYPE_IP;
263 goto uncompressed;
264
265 found:
266 /*
267 * Found it -- move to the front on the connection list.
268 */
269 if (cs == lastcs)
270 comp->last_cs = lcs;
271 else {
272 lcs->cs_next = cs->cs_next;
273 cs->cs_next = lastcs->cs_next;
274 lastcs->cs_next = cs;
275 }
276 }
277
278 /*
279 * Make sure that only what we expect to change changed. The first
280 * line of the `if' checks the IP protocol version, header length &
281 * type of service. The 2nd line checks the "Don't fragment" bit.
282 * The 3rd line checks the time-to-live and protocol (the protocol
283 * check is unnecessary but costless). The 4th line checks the TCP
284 * header length. The 5th line checks IP options, if any. The 6th
285 * line checks TCP options, if any. If any of these things are
286 * different between the previous & current datagram, we send the
287 * current datagram `uncompressed'.
288 */
289 oth = (struct tcphdr *)&((int32_t *)&cs->cs_ip)[hlen];
290 deltaS = hlen;
291 hlen += th->th_off;
292 hlen <<= 2;
293 if (hlen > m->m_len)
294 return TYPE_IP;
295
296 if (((u_int16_t *)ip)[0] != ((u_int16_t *)&cs->cs_ip)[0] ||
297 ((u_int16_t *)ip)[3] != ((u_int16_t *)&cs->cs_ip)[3] ||
298 ((u_int16_t *)ip)[4] != ((u_int16_t *)&cs->cs_ip)[4] ||
299 th->th_off != oth->th_off ||
300 (deltaS > 5 &&
301 BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
302 (th->th_off > 5 &&
303 BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))
304 goto uncompressed;
305
306 /*
307 * Figure out which of the changing fields changed. The
308 * receiver expects changes in the order: urgent, window,
309 * ack, seq (the order minimizes the number of temporaries
310 * needed in this section of code).
311 */
312 if (th->th_flags & TH_URG) {
313 deltaS = ntohs(th->th_urp);
314 ENCODEZ(deltaS);
315 changes |= NEW_U;
316 } else if (th->th_urp != oth->th_urp)
317 /* argh! URG not set but urp changed -- a sensible
318 * implementation should never do this but RFC793
319 * doesn't prohibit the change so we have to deal
320 * with it. */
321 goto uncompressed;
322
323 deltaS = (u_int16_t)(ntohs(th->th_win) - ntohs(oth->th_win));
324 if (deltaS) {
325 ENCODE(deltaS);
326 changes |= NEW_W;
327 }
328
329 deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack);
330 if (deltaA) {
331 if (deltaA > 0xffff)
332 goto uncompressed;
333 ENCODE(deltaA);
334 changes |= NEW_A;
335 }
336
337 deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq);
338 if (deltaS) {
339 if (deltaS > 0xffff)
340 goto uncompressed;
341 ENCODE(deltaS);
342 changes |= NEW_S;
343 }
344
345 switch(changes) {
346
347 case 0:
348 /*
349 * Nothing changed. If this packet contains data and the
350 * last one didn't, this is probably a data packet following
351 * an ack (normal on an interactive connection) and we send
352 * it compressed. Otherwise it's probably a retransmit,
353 * retransmitted ack or window probe. Send it uncompressed
354 * in case the other side missed the compressed version.
355 */
356 if (ip->ip_len != cs->cs_ip.ip_len &&
357 ntohs(cs->cs_ip.ip_len) == hlen)
358 break;
359
360 /* (fall through) */
361
362 case SPECIAL_I:
363 case SPECIAL_D:
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 if (deltaS == deltaA &&
372 deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
373 /* special case for echoed terminal traffic */
374 changes = SPECIAL_I;
375 cp = new_seq;
376 }
377 break;
378
379 case NEW_S:
380 if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
381 /* special case for data xfer */
382 changes = SPECIAL_D;
383 cp = new_seq;
384 }
385 break;
386 }
387
388 deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
389 if (deltaS != 1) {
390 ENCODEZ(deltaS);
391 changes |= NEW_I;
392 }
393 if (th->th_flags & TH_PUSH)
394 changes |= TCP_PUSH_BIT;
395 /*
396 * Grab the cksum before we overwrite it below. Then update our
397 * state with this packet's header.
398 */
399 deltaA = ntohs(th->th_sum);
400 BCOPY(ip, &cs->cs_ip, hlen);
401
402 /*
403 * We want to use the original packet as our compressed packet.
404 * (cp - new_seq) is the number of bytes we need for compressed
405 * sequence numbers. In addition we need one byte for the change
406 * mask, one for the connection id and two for the tcp checksum.
407 * So, (cp - new_seq) + 4 bytes of header are needed. hlen is how
408 * many bytes of the original packet to toss so subtract the two to
409 * get the new packet size.
410 */
411 deltaS = cp - new_seq;
412 cp = (u_char *)ip;
413 if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {
414 comp->last_xmit = cs->cs_id;
415 hlen -= deltaS + 4;
416 cp += hlen;
417 *cp++ = changes | NEW_C;
418 *cp++ = cs->cs_id;
419 } else {
420 hlen -= deltaS + 3;
421 cp += hlen;
422 *cp++ = changes;
423 }
424 m->m_len -= hlen;
425 m->m_data += hlen;
426 *cp++ = deltaA >> 8;
427 *cp++ = deltaA;
428 BCOPY(new_seq, cp, deltaS);
429 INCR(sls_compressed)
430 return (TYPE_COMPRESSED_TCP);
431
432 /*
433 * Update connection state cs & send uncompressed packet ('uncompressed'
434 * means a regular ip/tcp packet but with the 'conversation id' we hope
435 * to use on future compressed packets in the protocol field).
436 */
437 uncompressed:
438 BCOPY(ip, &cs->cs_ip, hlen);
439 ip->ip_p = cs->cs_id;
440 comp->last_xmit = cs->cs_id;
441 return (TYPE_UNCOMPRESSED_TCP);
442 }
443
444
445 int
446 sl_uncompress_tcp(bufp, len, type, comp)
447 u_char **bufp;
448 int len;
449 u_int type;
450 struct slcompress *comp;
451 {
452 u_char *hdr, *cp;
453 int hlen, vjlen;
454
455 cp = bufp? *bufp: NULL;
456 vjlen = sl_uncompress_tcp_core(cp, len, len, type, comp, &hdr, &hlen);
457 if (vjlen < 0)
458 return (0); /* error */
459 if (vjlen == 0)
460 return (len); /* was uncompressed already */
461
462 cp += vjlen;
463 len -= vjlen;
464
465 /*
466 * At this point, cp points to the first byte of data in the
467 * packet. If we're not aligned on a 4-byte boundary, copy the
468 * data down so the ip & tcp headers will be aligned. Then back up
469 * cp by the tcp/ip header length to make room for the reconstructed
470 * header (we assume the packet we were handed has enough space to
471 * prepend 128 bytes of header).
472 */
473 if ((intptr_t)cp & 3) {
474 if (len > 0)
475 (void) ovbcopy(cp, (caddr_t)((intptr_t)cp &~ 3), len);
476 cp = (u_char *)((intptr_t)cp &~ 3);
477 }
478 cp -= hlen;
479 len += hlen;
480 BCOPY(hdr, cp, hlen);
481
482 *bufp = cp;
483 return (len);
484 }
485
486 /*
487 * Uncompress a packet of total length total_len. The first buflen
488 * bytes are at buf; this must include the entire (compressed or
489 * uncompressed) TCP/IP header. This procedure returns the length
490 * of the VJ header, with a pointer to the uncompressed IP header
491 * in *hdrp and its length in *hlenp.
492 */
493 int
494 sl_uncompress_tcp_core(buf, buflen, total_len, type, comp, hdrp, hlenp)
495 u_char *buf;
496 int buflen, total_len;
497 u_int type;
498 struct slcompress *comp;
499 u_char **hdrp;
500 u_int *hlenp;
501 {
502 register u_char *cp;
503 register u_int hlen, changes;
504 register struct tcphdr *th;
505 register struct cstate *cs;
506 register struct ip *ip;
507 register u_int16_t *bp;
508 register u_int vjlen;
509
510 switch (type) {
511
512 case TYPE_UNCOMPRESSED_TCP:
513 ip = (struct ip *) buf;
514 if (ip->ip_p >= MAX_STATES)
515 goto bad;
516 cs = &comp->rstate[comp->last_recv = ip->ip_p];
517 comp->flags &=~ SLF_TOSS;
518 ip->ip_p = IPPROTO_TCP;
519 /*
520 * Calculate the size of the TCP/IP header and make sure that
521 * we don't overflow the space we have available for it.
522 */
523 hlen = ip->ip_hl << 2;
524 if (hlen + sizeof(struct tcphdr) > buflen)
525 goto bad;
526 hlen += ((struct tcphdr *)&((char *)ip)[hlen])->th_off << 2;
527 if (hlen > MAX_HDR || hlen > buflen)
528 goto bad;
529 BCOPY(ip, &cs->cs_ip, hlen);
530 cs->cs_hlen = hlen;
531 INCR(sls_uncompressedin)
532 *hdrp = (u_char *) &cs->cs_ip;
533 *hlenp = hlen;
534 return (0);
535
536 default:
537 goto bad;
538
539 case TYPE_COMPRESSED_TCP:
540 break;
541 }
542 /* We've got a compressed packet. */
543 INCR(sls_compressedin)
544 cp = buf;
545 changes = *cp++;
546 if (changes & NEW_C) {
547 /* Make sure the state index is in range, then grab the state.
548 * If we have a good state index, clear the 'discard' flag. */
549 if (*cp >= MAX_STATES)
550 goto bad;
551
552 comp->flags &=~ SLF_TOSS;
553 comp->last_recv = *cp++;
554 } else {
555 /* this packet has an implicit state index. If we've
556 * had a line error since the last time we got an
557 * explicit state index, we have to toss the packet. */
558 if (comp->flags & SLF_TOSS) {
559 INCR(sls_tossed)
560 return (-1);
561 }
562 }
563 cs = &comp->rstate[comp->last_recv];
564 hlen = cs->cs_ip.ip_hl << 2;
565 th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen];
566 th->th_sum = htons((*cp << 8) | cp[1]);
567 cp += 2;
568 if (changes & TCP_PUSH_BIT)
569 th->th_flags |= TH_PUSH;
570 else
571 th->th_flags &=~ TH_PUSH;
572
573 switch (changes & SPECIALS_MASK) {
574 case SPECIAL_I:
575 {
576 register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
577 th->th_ack = htonl(ntohl(th->th_ack) + i);
578 th->th_seq = htonl(ntohl(th->th_seq) + i);
579 }
580 break;
581
582 case SPECIAL_D:
583 th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
584 - cs->cs_hlen);
585 break;
586
587 default:
588 if (changes & NEW_U) {
589 th->th_flags |= TH_URG;
590 DECODEU(th->th_urp)
591 } else
592 th->th_flags &=~ TH_URG;
593 if (changes & NEW_W)
594 DECODES(th->th_win)
595 if (changes & NEW_A)
596 DECODEL(th->th_ack)
597 if (changes & NEW_S)
598 DECODEL(th->th_seq)
599 break;
600 }
601 if (changes & NEW_I) {
602 DECODES(cs->cs_ip.ip_id)
603 } else
604 cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
605
606 /*
607 * At this point, cp points to the first byte of data in the
608 * packet. Fill in the IP total length and update the IP
609 * header checksum.
610 */
611 vjlen = cp - buf;
612 buflen -= vjlen;
613 if (buflen < 0)
614 /* we must have dropped some characters (crc should detect
615 * this but the old slip framing won't) */
616 goto bad;
617
618 total_len += cs->cs_hlen - vjlen;
619 cs->cs_ip.ip_len = htons(total_len);
620
621 /* recompute the ip header checksum */
622 bp = (u_int16_t *) &cs->cs_ip;
623 cs->cs_ip.ip_sum = 0;
624 for (changes = 0; hlen > 0; hlen -= 2)
625 changes += *bp++;
626 changes = (changes & 0xffff) + (changes >> 16);
627 changes = (changes & 0xffff) + (changes >> 16);
628 cs->cs_ip.ip_sum = ~ changes;
629
630 *hdrp = (u_char *) &cs->cs_ip;
631 *hlenp = cs->cs_hlen;
632 return vjlen;
633
634 bad:
635 comp->flags |= SLF_TOSS;
636 INCR(sls_errorin)
637 return (-1);
638 }