Commit | Line | Data |
---|---|---|
11b5360c SL |
1 | /* slcompress.c 7.1 89/06/28 */ |
2 | ||
3 | /* | |
4 | * THIS CODE IS NOT FOR DISTRIBUTION! | |
5 | * KEEP YOUR GRUBBY HANDS OFF UNLESS AUTHORIZED BY VAN JACOBSON TO COPY! | |
6 | * ASK SAM, MIKE, OR BILL ABOUT IT. | |
7 | */ | |
8 | ||
9 | /* | |
10 | * Routines to compress and uncompess tcp packets (for transmission | |
11 | * over low speed serial lines. | |
12 | * | |
13 | * Copyright (c) 1988, 1989 by Van Jacobson, Lawrence Berkeley Laboratory | |
14 | * All rights reserved. | |
15 | */ | |
16 | ||
17 | #ifndef lint | |
18 | static char rcsid[] = "$Header: slcompress.c,v 1.7 89/03/19 18:10:19 van Locked $"; | |
19 | #endif | |
20 | ||
21 | #include <sys/types.h> | |
22 | #include <sys/param.h> | |
23 | #include <sys/mbuf.h> | |
24 | #include <netinet/in.h> | |
25 | #include <netinet/in_systm.h> | |
26 | #include <netinet/ip.h> | |
27 | #include <netinet/tcp.h> | |
28 | ||
29 | #include "slcompress.h" | |
30 | ||
31 | int sls_packets; | |
32 | int sls_searches; | |
33 | int sls_misses; | |
34 | int sls_compressed; | |
35 | int sls_ipin; | |
36 | int sls_uncompressedin; | |
37 | int sls_compressedin; | |
38 | ||
39 | #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n)) | |
40 | #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n)) | |
41 | ||
42 | #ifndef KERNEL | |
43 | extern struct mbuf *m_get(); | |
44 | #undef MGET | |
45 | #define MGET(m, w, t) ((m) = m_get((w), (t))) | |
46 | #endif | |
47 | ||
48 | #if BSD>=198810 | |
49 | #define m_off m_data | |
50 | #endif | |
51 | ||
52 | void | |
53 | sl_compress_init(comp) | |
54 | struct slcompress *comp; | |
55 | { | |
56 | register u_int i; | |
57 | register struct cstate *tstate = comp->tstate; | |
58 | ||
59 | bzero((char *)comp, sizeof(*comp)); | |
60 | for (i = MAX_STATES - 1; i > 0; --i) { | |
61 | tstate[i].cs_id = i; | |
62 | tstate[i].cs_next = &tstate[i - 1]; | |
63 | } | |
64 | tstate[0].cs_next = &tstate[MAX_STATES - 1]; | |
65 | tstate[0].cs_id = 0; | |
66 | comp->last_cs = &tstate[0]; | |
67 | comp->last_recv = 255; | |
68 | comp->last_xmit = 255; | |
69 | } | |
70 | ||
71 | ||
72 | /* ENCODE encodes a number that is known to be non-zero. ENCODEZ | |
73 | * checks for zero (since zero has to be encoded in the long, 3 byte | |
74 | * form). | |
75 | */ | |
76 | #define ENCODE(n) { \ | |
77 | if ((u_short)(n) >= 256) { \ | |
78 | *cp++ = 0; \ | |
79 | cp[1] = (n); \ | |
80 | cp[0] = (n) >> 8; \ | |
81 | cp += 2; \ | |
82 | } else { \ | |
83 | *cp++ = (n); \ | |
84 | } \ | |
85 | } | |
86 | #define ENCODEZ(n) { \ | |
87 | if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \ | |
88 | *cp++ = 0; \ | |
89 | cp[1] = (n); \ | |
90 | cp[0] = (n) >> 8; \ | |
91 | cp += 2; \ | |
92 | } else { \ | |
93 | *cp++ = (n); \ | |
94 | } \ | |
95 | } | |
96 | ||
97 | #define DECODEL(f) { \ | |
98 | if (*cp == 0) {\ | |
99 | (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \ | |
100 | cp += 3; \ | |
101 | } else { \ | |
102 | (f) = htonl(ntohl(f) + (u_long)*cp++); \ | |
103 | } \ | |
104 | } | |
105 | ||
106 | #define DECODES(f) { \ | |
107 | if (*cp == 0) {\ | |
108 | (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \ | |
109 | cp += 3; \ | |
110 | } else { \ | |
111 | (f) = htons(ntohs(f) + (u_long)*cp++); \ | |
112 | } \ | |
113 | } | |
114 | ||
115 | ||
116 | u_char | |
117 | sl_compress_tcp(m, ip, comp) | |
118 | struct mbuf *m; | |
119 | register struct ip *ip; | |
120 | struct slcompress *comp; | |
121 | { | |
122 | register struct cstate *cs = comp->last_cs->cs_next; | |
123 | register u_int hlen = ip->ip_hl; | |
124 | register struct tcphdr *oth; | |
125 | register struct tcphdr *th; | |
126 | register u_int deltaS, deltaA; | |
127 | register u_int changes = 0; | |
128 | u_char new_seq[16]; | |
129 | register u_char *cp = new_seq; | |
130 | ||
131 | /* | |
132 | * Bail if this is an ip fragment or if we don't have | |
133 | * a complete ip & tcp header in the first mbuf. Otherwise, | |
134 | * check flags to see if this is a packet we might compress | |
135 | * and, if so, try to locate the connection state. | |
136 | * since slip links tend to be end nodes, check the tcp ports | |
137 | * first since the inet addresses won't usually change. | |
138 | * special case the most recently used connection since | |
139 | * it's most likely to be used again & we don't have to | |
140 | * do any reordering if it's used. | |
141 | */ | |
142 | if ((ip->ip_off & 0x3fff) || m->m_len < 40) | |
143 | return (TYPE_IP); | |
144 | ||
145 | th = (struct tcphdr *)&((int *)ip)[hlen]; | |
146 | if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK) | |
147 | return (TYPE_IP); | |
148 | ||
149 | ++sls_packets; | |
150 | if (*(int *)th != ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl] || | |
151 | ip->ip_src.s_addr != cs->cs_ip.ip_src.s_addr || | |
152 | ip->ip_dst.s_addr != cs->cs_ip.ip_dst.s_addr) { | |
153 | /* | |
154 | * Wasn't the first -- search for it. | |
155 | * | |
156 | * States are kept in a circularly linked list with | |
157 | * first_cs pointing to the head of the list. The | |
158 | * list is kept in lru order by moving a state to the | |
159 | * head of the list whenever it is referenced. Since | |
160 | * the list is short and, empirically, the connection | |
161 | * we want is almost always near the front, we locate | |
162 | * states via linear search. If we don't find a state | |
163 | * for the datagram, the oldest state is used. | |
164 | */ | |
165 | register struct cstate *lcs; | |
166 | ||
167 | do { | |
168 | lcs = cs; cs = cs->cs_next; | |
169 | ++sls_searches; | |
170 | if (*(int *)th == ((int *)&cs->cs_ip)[cs->cs_ip.ip_hl] | |
171 | && ip->ip_src.s_addr == cs->cs_ip.ip_src.s_addr | |
172 | && ip->ip_dst.s_addr == cs->cs_ip.ip_dst.s_addr) | |
173 | goto found; | |
174 | } while (cs != comp->last_cs); | |
175 | ++sls_misses; | |
176 | ||
177 | /* | |
178 | * Didn't find it -- re-use oldest cstate. | |
179 | * Send an uncompressed packet that tells | |
180 | * the other side what connection number | |
181 | * we're using for this conversation. Note | |
182 | * that since the state list is circular, the | |
183 | * oldest state points to the newest and we only | |
184 | * need to set last_cs to update the lru linkage. | |
185 | */ | |
186 | comp->last_cs = lcs; | |
187 | hlen += th->th_off; | |
188 | hlen <<= 2; | |
189 | goto uncompressed; | |
190 | ||
191 | found: | |
192 | /* | |
193 | * Found it -- move to the front on the connection list. | |
194 | */ | |
195 | if (comp->last_cs == cs) | |
196 | comp->last_cs = lcs; | |
197 | else { | |
198 | lcs->cs_next = cs->cs_next; | |
199 | cs->cs_next = comp->last_cs->cs_next; | |
200 | comp->last_cs->cs_next = cs; | |
201 | } | |
202 | } | |
203 | ||
204 | /* | |
205 | * Make sure that only what we expect to change changed. | |
206 | */ | |
207 | oth = (struct tcphdr *)&((int *)&cs->cs_ip)[hlen]; | |
208 | deltaS = hlen; | |
209 | hlen += th->th_off; | |
210 | hlen <<= 2; | |
211 | ||
212 | if (((u_short *)ip)[0] != ((u_short *)&cs->cs_ip)[0] || | |
213 | ((u_short *)ip)[4] != ((u_short *)&cs->cs_ip)[4] || | |
214 | th->th_off != oth->th_off || | |
215 | (deltaS > 5 && | |
216 | BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) || | |
217 | (th->th_off > 5 && | |
218 | BCMP(th + 1, oth + 1, (th->th_off - 5) << 2))) | |
219 | goto uncompressed; | |
220 | ||
221 | /* | |
222 | * Figure out which of the changing fields changed. The | |
223 | * receiver expects changes in the order: urgent, window, | |
224 | * ack, seq (the order minimizes the number of temporaries | |
225 | * needed in this section of code). | |
226 | */ | |
227 | if (th->th_flags & TH_URG) { | |
228 | deltaS = ntohs(th->th_urp); | |
229 | ENCODEZ(deltaS); | |
230 | changes |= NEW_U; | |
231 | } else if (th->th_urp != oth->th_urp) | |
232 | /* argh! URG not set but urp changed -- a sensible | |
233 | * implementation should never do this but RFC793 | |
234 | * doesn't prohibit the change so we have to deal | |
235 | * with it. */ | |
236 | goto uncompressed; | |
237 | ||
238 | if (deltaS = (u_short)(ntohs(th->th_win) - ntohs(oth->th_win))) { | |
239 | ENCODE(deltaS); | |
240 | changes |= NEW_W; | |
241 | } | |
242 | ||
243 | if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) { | |
244 | if (deltaA > 0xffff) | |
245 | goto uncompressed; | |
246 | ENCODE(deltaA); | |
247 | changes |= NEW_A; | |
248 | } | |
249 | ||
250 | if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) { | |
251 | if (deltaS > 0xffff) | |
252 | goto uncompressed; | |
253 | ENCODE(deltaS); | |
254 | changes |= NEW_S; | |
255 | } | |
256 | ||
257 | switch(changes) { | |
258 | ||
259 | case 0: | |
260 | if (ip->ip_len != cs->cs_ip.ip_len && ntohs(ip->ip_len) != hlen) | |
261 | break; | |
262 | /* | |
263 | * Nothing changed and this packet looks like a duplicate | |
264 | * of the last or contains no data -- this is probably a | |
265 | * retransmitted ack or window probe. Send it | |
266 | * uncompressed in case the other side missed the | |
267 | * compressed version. | |
268 | * | |
269 | * (fall through) | |
270 | */ | |
271 | ||
272 | case SPECIAL_I: | |
273 | case SPECIAL_D: | |
274 | /* | |
275 | * actual changes match one of our special case encodings -- | |
276 | * send packet uncompressed. | |
277 | */ | |
278 | goto uncompressed; | |
279 | ||
280 | case NEW_S|NEW_A: | |
281 | if (deltaS == deltaA && | |
282 | deltaS == ntohs(cs->cs_ip.ip_len) - hlen) { | |
283 | /* special case for echoed terminal traffic */ | |
284 | changes = SPECIAL_I; | |
285 | cp = new_seq; | |
286 | } | |
287 | break; | |
288 | ||
289 | case NEW_S: | |
290 | if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) { | |
291 | /* special case for data xfer */ | |
292 | changes = SPECIAL_D; | |
293 | cp = new_seq; | |
294 | } | |
295 | break; | |
296 | } | |
297 | ||
298 | deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id); | |
299 | if (deltaS != 1) { | |
300 | ENCODEZ(deltaS); | |
301 | changes |= NEW_I; | |
302 | } | |
303 | if (th->th_flags & TH_PUSH) | |
304 | changes |= TCP_PUSH_BIT; | |
305 | /* | |
306 | * Grab the cksum before we overwrite it below. Then update our | |
307 | * state with this packet's header. | |
308 | */ | |
309 | deltaA = ntohs(th->th_sum); | |
310 | BCOPY(ip, &cs->cs_ip, hlen); | |
311 | ||
312 | /* | |
313 | * We want to use the original packet as our compressed packet. | |
314 | * (cp - new_seq) is the number of bytes we need for compressed | |
315 | * sequence numbers. In addition we need one byte for the change | |
316 | * mask, one for the connection id and two for the tcp checksum. | |
317 | * So, (cp - new_seq) + 4 bytes of header are needed. hlen is how | |
318 | * many bytes of the original packet to toss so subtract the two to | |
319 | * get the new packet size. | |
320 | */ | |
321 | deltaS = cp - new_seq; | |
322 | cp = (u_char *)ip; | |
323 | if (comp->last_xmit != cs->cs_id) { | |
324 | comp->last_xmit = cs->cs_id; | |
325 | hlen -= deltaS + 4; | |
326 | cp += hlen; m->m_len -= hlen; m->m_off += hlen; | |
327 | *cp++ = changes | NEW_C; | |
328 | *cp++ = cs->cs_id; | |
329 | } else { | |
330 | hlen -= deltaS + 3; | |
331 | cp += hlen; m->m_len -= hlen; m->m_off += hlen; | |
332 | *cp++ = changes; | |
333 | } | |
334 | *cp++ = deltaA >> 8; | |
335 | *cp++ = deltaA; | |
336 | BCOPY(new_seq, cp, deltaS); | |
337 | ++sls_compressed; | |
338 | /* note: low order version bits used */ | |
339 | ip = mtod(m, struct ip *); | |
340 | ip->ip_v |= (TYPE_COMPRESSED_TCP>>4); | |
341 | return (TYPE_COMPRESSED_TCP); | |
342 | ||
343 | /* | |
344 | * Update connection state cs & send uncompressed packet ('uncompressed' | |
345 | * means a regular ip/tcp packet but with the 'conversation id' we hope | |
346 | * to use on future compressed packets in the protocol field). | |
347 | */ | |
348 | uncompressed: | |
349 | BCOPY(ip, &cs->cs_ip, hlen); | |
350 | ip->ip_p = cs->cs_id; | |
351 | comp->last_xmit = cs->cs_id; | |
352 | ip->ip_v = (TYPE_UNCOMPRESSED_TCP>>4); | |
353 | return (TYPE_UNCOMPRESSED_TCP); | |
354 | } | |
355 | ||
356 | int uncdeb ; | |
357 | ||
358 | struct mbuf * | |
359 | sl_uncompress_tcp(m, type, comp) | |
360 | register struct mbuf *m; | |
361 | u_char type; | |
362 | struct slcompress *comp; | |
363 | { | |
364 | register u_char *cp; | |
365 | register u_int hlen, changes; | |
366 | register struct tcphdr *th; | |
367 | register struct cstate *cs; | |
368 | register struct ip *ip; | |
369 | register struct mbuf *m0; | |
370 | ||
371 | switch (type) { | |
372 | ||
373 | case TYPE_UNCOMPRESSED_TCP: | |
374 | ip = mtod(m, struct ip *); | |
375 | if (ip->ip_p >= MAX_STATES) | |
376 | goto bad; | |
377 | ip->ip_v = 4; | |
378 | ||
379 | cs = &comp->rstate[comp->last_recv = ip->ip_p]; | |
380 | comp->flags &=~ SLF_TOSS; | |
381 | ip->ip_p = IPPROTO_TCP; | |
382 | hlen = ip->ip_hl; | |
383 | hlen += ((struct tcphdr *)&((int *)ip)[hlen])->th_off; | |
384 | hlen <<= 2; | |
385 | BCOPY(ip, &cs->cs_ip, hlen); | |
386 | cs->cs_ip.ip_sum = 0; | |
387 | cs->cs_hlen = hlen; | |
388 | ++sls_uncompressedin; | |
389 | return (m); | |
390 | ||
391 | default: | |
392 | if(type&TYPE_COMPRESSED_TCP) goto compre; | |
393 | ++sls_ipin; | |
394 | return (m); | |
395 | ||
396 | case TYPE_ERROR: | |
397 | comp->flags |= SLF_TOSS; | |
398 | return (m); | |
399 | ||
400 | case TYPE_COMPRESSED_TCP: | |
401 | compre: | |
402 | break; | |
403 | } | |
404 | /* We've got a compressed packet. */ | |
405 | ++sls_compressedin; | |
406 | cp = mtod(m, u_char *); | |
407 | changes = *cp++; | |
408 | if (changes & NEW_C) { | |
409 | /* Make sure the state index is in range, then grab the state. | |
410 | * If we have a good state index, clear the 'discard' flag. */ | |
411 | if (*cp >= MAX_STATES) | |
412 | goto bad; | |
413 | ||
414 | comp->flags &=~ SLF_TOSS; | |
415 | comp->last_recv = *cp++; | |
416 | } else { | |
417 | /* this packet has an implicit state index. If we've | |
418 | * had a line error since the last time we got an | |
419 | * explicit state index, we have to toss the packet. */ | |
420 | if (comp->flags & SLF_TOSS) | |
421 | goto bad; | |
422 | } | |
423 | cs = &comp->rstate[comp->last_recv]; | |
424 | hlen = cs->cs_ip.ip_hl << 2; | |
425 | th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen]; | |
426 | th->th_sum = htons((*cp << 8) | cp[1]); | |
427 | cp += 2; | |
428 | if (changes & TCP_PUSH_BIT) | |
429 | th->th_flags |= TH_PUSH; | |
430 | else | |
431 | th->th_flags &=~ TH_PUSH; | |
432 | ||
433 | switch (changes & SPECIALS_MASK) { | |
434 | case SPECIAL_I: | |
435 | { | |
436 | register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen; | |
437 | th->th_ack = htonl(ntohl(th->th_ack) + i); | |
438 | th->th_seq = htonl(ntohl(th->th_seq) + i); | |
439 | } | |
440 | break; | |
441 | ||
442 | case SPECIAL_D: | |
443 | th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len) | |
444 | - cs->cs_hlen); | |
445 | break; | |
446 | ||
447 | default: | |
448 | if (changes & NEW_U) { | |
449 | th->th_flags |= TH_URG; | |
450 | DECODES(th->th_urp) | |
451 | } else | |
452 | th->th_flags &=~ TH_URG; | |
453 | if (changes & NEW_W) | |
454 | DECODES(th->th_win) | |
455 | if (changes & NEW_A) | |
456 | DECODEL(th->th_ack) | |
457 | if (changes & NEW_S) | |
458 | DECODEL(th->th_seq) | |
459 | break; | |
460 | } | |
461 | if (changes & NEW_I) { | |
462 | DECODES(cs->cs_ip.ip_id) | |
463 | } else | |
464 | cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1); | |
465 | ||
466 | /* | |
467 | * At this point, cp points to the first byte of data in the | |
468 | * packet (if any). Toss the compressed header from the | |
469 | * original packet, allocatate a new mbuf for the uncompressed | |
470 | * header (to make sure it's aligned correctly), then chain it | |
471 | * in front of the original. Set up the ip length & ip checksum then | |
472 | * return the rebuilt packet. | |
473 | */ | |
474 | changes = cp - mtod(m, u_char *); | |
475 | m->m_off += changes; m->m_len -= changes; | |
476 | changes = cs->cs_hlen; | |
477 | for (m0 = m; m0; m0 = m0->m_next) | |
478 | changes += m0->m_len; | |
479 | cs->cs_ip.ip_len = htons(changes); | |
480 | ||
481 | /*MGET(m0, M_DONTWAIT, MT_DATA);*/ | |
482 | MGETHDR(m0, M_DONTWAIT, MT_DATA); /* XXX! */ | |
483 | if (! m0) | |
484 | goto bad; | |
485 | ||
486 | m0->m_next = m; | |
487 | m0->m_pkthdr.rcvif = m->m_pkthdr.rcvif ; /* XXX! */ | |
488 | m0->m_pkthdr.len = m->m_pkthdr.len; /* XXX! */ | |
489 | m = m0; | |
490 | m->m_len = cs->cs_hlen; | |
491 | ip = mtod(m, struct ip *); | |
492 | BCOPY(&cs->cs_ip, ip, cs->cs_hlen); | |
493 | ||
494 | ip->ip_sum = in_cksum(m, hlen); | |
495 | return (m); | |
496 | ||
497 | bad: | |
498 | m_freem(m); | |
499 | return ((struct mbuf *)0); | |
500 | } |