slcompress.c revision 30187
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.10 1997/08/25 00:29:28 brian Exp $ 21 * 22 * Van Jacobson (van@helios.ee.lbl.gov), Dec 31, 1989: 23 * - Initial distribution. 24 */ 25#ifndef lint 26static char const rcsid[] = "$Id: slcompress.c,v 1.10 1997/08/25 00:29:28 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 39struct 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 49void 50sl_compress_init(struct slcompress * comp, int max_state) 51{ 52 register u_int i; 53 register struct cstate *tstate = comp->tstate; 54 55 bzero((char *) comp, sizeof(*comp)); 56 for (i = max_state; 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_state]; 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 122u_char 123sl_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 206found: 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 if (comp->last_xmit == cs->cs_id && compress_cid) { 363 hlen -= deltaS + 3; 364 cp += hlen; 365 *cp++ = changes; 366 } else { 367 comp->last_xmit = cs->cs_id; 368 hlen -= deltaS + 4; 369 cp += hlen; 370 *cp++ = changes | NEW_C; 371 *cp++ = cs->cs_id; 372 } 373 m->cnt -= hlen; 374 m->offset += hlen; 375 *cp++ = deltaA >> 8; 376 *cp++ = deltaA; 377 BCOPY(new_seq, cp, deltaS); 378 INCR(sls_compressed) 379 return (TYPE_COMPRESSED_TCP); 380 381 /* 382 * Update connection state cs & send uncompressed packet ('uncompressed' 383 * means a regular ip/tcp packet but with the 'conversation id' we hope to 384 * use on future compressed packets in the protocol field). 385 */ 386uncompressed: 387 BCOPY(ip, &cs->cs_ip, hlen); 388 ip->ip_p = cs->cs_id; 389 comp->last_xmit = cs->cs_id; 390 return (TYPE_UNCOMPRESSED_TCP); 391} 392 393 394int 395sl_uncompress_tcp(u_char ** bufp, 396 int len, 397 u_int type, 398 struct slcompress * comp) 399{ 400 register u_char *cp; 401 register u_int hlen, changes; 402 register struct tcphdr *th; 403 register struct cstate *cs; 404 register struct ip *ip; 405 406 switch (type) { 407 408 case TYPE_UNCOMPRESSED_TCP: 409 ip = (struct ip *) * bufp; 410 if (ip->ip_p >= MAX_STATES) 411 goto bad; 412 cs = &comp->rstate[comp->last_recv = ip->ip_p]; 413 comp->flags &= ~SLF_TOSS; 414 ip->ip_p = IPPROTO_TCP; 415 416 /* 417 * Calculate the size of the TCP/IP header and make sure that we don't 418 * overflow the space we have available for it. 419 */ 420 hlen = ip->ip_hl << 2; 421 if (hlen + sizeof(struct tcphdr) > len) 422 goto bad; 423 th = (struct tcphdr *) & ((char *) ip)[hlen]; 424 hlen += THOFFSET(th) << 2; 425 if (hlen > MAX_HDR) 426 goto bad; 427 BCOPY(ip, &cs->cs_ip, hlen); 428 /* cs->cs_ip.ip_sum = 0; */ 429 cs->cs_hlen = hlen; 430 INCR(sls_uncompressedin) 431 return (len); 432 433 default: 434 goto bad; 435 436 case TYPE_COMPRESSED_TCP: 437 break; 438 } 439 /* We've got a compressed packet. */ 440 INCR(sls_compressedin) 441 cp = *bufp; 442 changes = *cp++; 443 LogPrintf(LogDEBUG, "compressed: changes = %02x\n", changes); 444 if (changes & NEW_C) { 445 446 /* 447 * Make sure the state index is in range, then grab the state. If we have 448 * a good state index, clear the 'discard' flag. 449 */ 450 if (*cp >= MAX_STATES || comp->last_recv == 255) 451 goto bad; 452 453 comp->flags &= ~SLF_TOSS; 454 comp->last_recv = *cp++; 455 } else { 456 457 /* 458 * this packet has an implicit state index. If we've had a line error 459 * since the last time we got an explicit state index, we have to toss 460 * the packet. 461 */ 462 if (comp->flags & SLF_TOSS) { 463 INCR(sls_tossed) 464 return (0); 465 } 466 } 467 cs = &comp->rstate[comp->last_recv]; 468 hlen = cs->cs_ip.ip_hl << 2; 469 th = (struct tcphdr *) & ((u_char *) & cs->cs_ip)[hlen]; 470 th->th_sum = htons((*cp << 8) | cp[1]); 471 cp += 2; 472 if (changes & TCP_PUSH_BIT) 473 th->th_flags |= TH_PUSH; 474 else 475 th->th_flags &= ~TH_PUSH; 476 477 switch (changes & SPECIALS_MASK) { 478 case SPECIAL_I: 479 { 480 register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen; 481 482 th->th_ack = htonl(ntohl(th->th_ack) + i); 483 th->th_seq = htonl(ntohl(th->th_seq) + i); 484 } 485 break; 486 487 case SPECIAL_D: 488 th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len) 489 - cs->cs_hlen); 490 break; 491 492 default: 493 if (changes & NEW_U) { 494 th->th_flags |= TH_URG; 495 DECODEU(th->th_urp) 496 } else 497 th->th_flags &= ~TH_URG; 498 if (changes & NEW_W) 499 DECODES(th->th_win) 500 if (changes & NEW_A) 501 DECODEL(th->th_ack) 502 if (changes & NEW_S) { 503 LogPrintf(LogDEBUG, "NEW_S: %02x, %02x, %02x\n", 504 *cp, cp[1], cp[2]); 505 DECODEL(th->th_seq) 506 } 507 break; 508 } 509 if (changes & NEW_I) { 510 DECODES(cs->cs_ip.ip_id) 511 } else 512 cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1); 513 514 LogPrintf(LogDEBUG, "Uncompress: id = %04x, seq = %08x\n", 515 cs->cs_ip.ip_id, ntohl(th->th_seq)); 516 517 /* 518 * At this point, cp points to the first byte of data in the packet. If 519 * we're not aligned on a 4-byte boundary, copy the data down so the ip & 520 * tcp headers will be aligned. Then back up cp by the tcp/ip header 521 * length to make room for the reconstructed header (we assume the packet 522 * we were handed has enough space to prepend 128 bytes of header). Adjust 523 * the length to account for the new header & fill in the IP total length. 524 */ 525 len -= (cp - *bufp); 526 if (len < 0) 527 528 /* 529 * we must have dropped some characters (crc should detect this but the 530 * old slip framing won't) 531 */ 532 goto bad; 533 534#ifdef notdef 535 if ((int) cp & 3) { 536 if (len > 0) 537 (void) ovbcopy(cp, (caddr_t) ((int) cp & ~3), len); 538 cp = (u_char *) ((int) cp & ~3); 539 } 540#endif 541 542 cp -= cs->cs_hlen; 543 len += cs->cs_hlen; 544 cs->cs_ip.ip_len = htons(len); 545 BCOPY(&cs->cs_ip, cp, cs->cs_hlen); 546 *bufp = cp; 547 548 /* recompute the ip header checksum */ 549 { 550 register u_short *bp = (u_short *) cp; 551 552 cs->cs_ip.ip_sum = 0; 553 for (changes = 0; hlen > 0; hlen -= 2) 554 changes += *bp++; 555 changes = (changes & 0xffff) + (changes >> 16); 556 changes = (changes & 0xffff) + (changes >> 16); 557 ((struct ip *) cp)->ip_sum = ~changes; 558 } 559 return (len); 560bad: 561 comp->flags |= SLF_TOSS; 562 INCR(sls_errorin) 563 return (0); 564} 565 566int 567ReportCompress() 568{ 569 if (!VarTerm) 570 return 1; 571 572 fprintf(VarTerm, "Out: %d (compress) / %d (total)", 573 slstat.sls_compressed, slstat.sls_packets); 574 fprintf(VarTerm, " %d (miss) / %d (search)\n", 575 slstat.sls_misses, slstat.sls_searches); 576 fprintf(VarTerm, "In: %d (compress), %d (uncompress)", 577 slstat.sls_compressedin, slstat.sls_uncompressedin); 578 fprintf(VarTerm, " %d (error), %d (tossed)\n", 579 slstat.sls_errorin, slstat.sls_tossed); 580 return 0; 581} 582