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