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