usr.sbin/ppp/slcompress.c

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