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