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