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