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