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