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