Return to slcompress.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / sys / net

Annotation of 43BSDReno/sys/net/slcompress.c, revision 1.1

1.1     ! root        1: /*     slcompress.c    7.6     90/06/28        */
        !             2: /*
        !             3:  * Routines to compress and uncompess tcp packets (for transmission
        !             4:  * over low speed serial lines.
        !             5:  *
        !             6:  * Copyright (c) 1989 Regents of the University of California.
        !             7:  * All rights reserved.
        !             8:  *
        !             9:  * Redistribution is only permitted until one year after the first shipment
        !            10:  * of 4.4BSD by the Regents.  Otherwise, redistribution and use in source and
        !            11:  * binary forms are permitted provided that: (1) source distributions retain
        !            12:  * this entire copyright notice and comment, and (2) distributions including
        !            13:  * binaries display the following acknowledgement:  This product includes
        !            14:  * software developed by the University of California, Berkeley and its
        !            15:  * contributors'' in the documentation or other materials provided with the
        !            16:  * distribution and in all advertising materials mentioning features or use
        !            17:  * of this software.  Neither the name of the University nor the names of
        !            18:  * its contributors may be used to endorse or promote products derived from
        !            19:  * this software without specific prior written permission.
        !            20:  * THIS SOFTWARE IS PROVIDED AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
        !            21:  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
        !            22:  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
        !            23:  *
        !            24:  *     Van Jacobson ([email protected]), Dec 31, 1989:
        !            25:  *     - Initial distribution.
        !            26:  */
        !            27: #ifndef lint
        !            28: static char rcsid[] = "$Header: slcompress.c,v 1.19 89/12/31 08:52:59 van Exp $";
        !            29: #endif
        !            30: 
        !            31: #include <sys/types.h>
        !            32: #include <sys/param.h>
        !            33: #include <sys/mbuf.h>
        !            34: #include <netinet/in.h>
        !            35: #include <netinet/in_systm.h>
        !            36: #include <netinet/ip.h>
        !            37: #include <netinet/tcp.h>
        !            38: 
        !            39: #include "slcompress.h"
        !            40: 
        !            41: #ifndef SL_NO_STATS
        !            42: #define INCR(counter) ++comp->counter;
        !            43: #else
        !            44: #define INCR(counter)
        !            45: #endif
        !            46: 
        !            47: #define BCMP(p1, p2, n) bcmp((char *)(p1), (char *)(p2), (int)(n))
        !            48: #define BCOPY(p1, p2, n) bcopy((char *)(p1), (char *)(p2), (int)(n))
        !            49: #ifndef KERNEL
        !            50: #define ovbcopy bcopy
        !            51: #endif
        !            52: 
        !            53: 
        !            54: void
        !            55: sl_compress_init(comp)
        !            56:        struct slcompress *comp;
        !            57: {
        !            58:        register u_int i;
        !            59:        register struct cstate *tstate = comp->tstate;
        !            60: 
        !            61:        bzero((char *)comp, sizeof(*comp));
        !            62:        for (i = MAX_STATES - 1; i > 0; --i) {
        !            63:                tstate[i].cs_id = i;
        !            64:                tstate[i].cs_next = &tstate[i - 1];
        !            65:        }
        !            66:        tstate[0].cs_next = &tstate[MAX_STATES - 1];
        !            67:        tstate[0].cs_id = 0;
        !            68:        comp->last_cs = &tstate[0];
        !            69:        comp->last_recv = 255;
        !            70:        comp->last_xmit = 255;
        !            71: }
        !            72: 
        !            73: 
        !            74: /* ENCODE encodes a number that is known to be non-zero.  ENCODEZ
        !            75:  * checks for zero (since zero has to be encoded in the long, 3 byte
        !            76:  * form).
        !            77:  */
        !            78: #define ENCODE(n) { \
        !            79:        if ((u_short)(n) >= 256) { \
        !            80:                *cp++ = 0; \
        !            81:                cp[1] = (n); \
        !            82:                cp[0] = (n) >> 8; \
        !            83:                cp += 2; \
        !            84:        } else { \
        !            85:                *cp++ = (n); \
        !            86:        } \
        !            87: }
        !            88: #define ENCODEZ(n) { \
        !            89:        if ((u_short)(n) >= 256 || (u_short)(n) == 0) { \
        !            90:                *cp++ = 0; \
        !            91:                cp[1] = (n); \
        !            92:                cp[0] = (n) >> 8; \
        !            93:                cp += 2; \
        !            94:        } else { \
        !            95:                *cp++ = (n); \
        !            96:        } \
        !            97: }
        !            98: 
        !            99: #define DECODEL(f) { \
        !           100:        if (*cp == 0) {\
        !           101:                (f) = htonl(ntohl(f) + ((cp[1] << 8) | cp[2])); \
        !           102:                cp += 3; \
        !           103:        } else { \
        !           104:                (f) = htonl(ntohl(f) + (u_long)*cp++); \
        !           105:        } \
        !           106: }
        !           107: 
        !           108: #define DECODES(f) { \
        !           109:        if (*cp == 0) {\
        !           110:                (f) = htons(ntohs(f) + ((cp[1] << 8) | cp[2])); \
        !           111:                cp += 3; \
        !           112:        } else { \
        !           113:                (f) = htons(ntohs(f) + (u_long)*cp++); \
        !           114:        } \
        !           115: }
        !           116: 
        !           117: #define DECODEU(f) { \
        !           118:        if (*cp == 0) {\
        !           119:                (f) = htons((cp[1] << 8) | cp[2]); \
        !           120:                cp += 3; \
        !           121:        } else { \
        !           122:                (f) = htons((u_long)*cp++); \
        !           123:        } \
        !           124: }
        !           125: 
        !           126: 
        !           127: u_char
        !           128: sl_compress_tcp(m, ip, comp, compress_cid)
        !           129:        struct mbuf *m;
        !           130:        register struct ip *ip;
        !           131:        struct slcompress *comp;
        !           132:        int compress_cid;
        !           133: {
        !           134:        register struct cstate *cs = comp->last_cs->cs_next;
        !           135:        register u_int hlen = ip->ip_hl;
        !           136:        register struct tcphdr *oth;
        !           137:        register struct tcphdr *th;
        !           138:        register u_int deltaS, deltaA;
        !           139:        register u_int changes = 0;
        !           140:        u_char new_seq[16];
        !           141:        register u_char *cp = new_seq;
        !           142: 
        !           143:        /*
        !           144:         * Bail if this is an IP fragment or if the TCP packet isn't
        !           145:         * `compressible' (i.e., ACK isn't set or some other control bit is
        !           146:         * set).  (We assume that the caller has already made sure the
        !           147:         * packet is IP proto TCP).
        !           148:         */
        !           149:        if ((ip->ip_off & htons(0x3fff)) || m->m_len < 40)
        !           150:                return (TYPE_IP);
        !           151: 
        !           152:        th = (struct tcphdr *)&((int *)ip)[hlen];
        !           153:        if ((th->th_flags & (TH_SYN|TH_FIN|TH_RST|TH_ACK)) != TH_ACK)
        !           154:                return (TYPE_IP);
        !           155:        /*
        !           156:         * Packet is compressible -- we're going to send either a
        !           157:         * COMPRESSED_TCP or UNCOMPRESSED_TCP packet.  Either way we need
        !           158:         * to locate (or create) the connection state.  Special case the
        !           159:         * most recently used connection since it's most likely to be used
        !           160:         * again & we don't have to do any reordering 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:                 * Wasn't the first -- search for it.
        !           168:                 *
        !           169:                 * States are kept in a circularly linked list with
        !           170:                 * last_cs pointing to the end of the list.  The
        !           171:                 * list is kept in lru order by moving a state to the
        !           172:                 * head of the list whenever it is referenced.  Since
        !           173:                 * the list is short and, empirically, the connection
        !           174:                 * we want is almost always near the front, we locate
        !           175:                 * states via linear search.  If we don't find a state
        !           176:                 * for the datagram, the oldest state is (re-)used.
        !           177:                 */
        !           178:                register struct cstate *lcs;
        !           179:                register struct cstate *lastcs = comp->last_cs;
        !           180: 
        !           181:                do {
        !           182:                        lcs = cs; 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
        !           192:                 * uncompressed packet that tells the other side what
        !           193:                 * connection number we're using for this conversation.
        !           194:                 * Note that since the state list is circular, the oldest
        !           195:                 * state points to the newest and we only need to set
        !           196:                 * last_cs to update the lru linkage.
        !           197:                 */
        !           198:                INCR(sls_misses)
        !           199:                comp->last_cs = lcs;
        !           200:                hlen += th->th_off;
        !           201:                hlen <<= 2;
        !           202:                goto uncompressed;
        !           203: 
        !           204:        found:
        !           205:                /*
        !           206:                 * Found it -- move to the front on the connection list.
        !           207:                 */
        !           208:                if (cs == lastcs)
        !           209:                        comp->last_cs = lcs;
        !           210:                else {
        !           211:                        lcs->cs_next = cs->cs_next;
        !           212:                        cs->cs_next = lastcs->cs_next;
        !           213:                        lastcs->cs_next = cs;
        !           214:                }
        !           215:        }
        !           216: 
        !           217:        /*
        !           218:         * Make sure that only what we expect to change changed. The first
        !           219:         * line of the `if' checks the IP protocol version, header length &
        !           220:         * type of service.  The 2nd line checks the "Don't fragment" bit.
        !           221:         * The 3rd line checks the time-to-live and protocol (the protocol
        !           222:         * check is unnecessary but costless).  The 4th line checks the TCP
        !           223:         * header length.  The 5th line checks IP options, if any.  The 6th
        !           224:         * line checks TCP options, if any.  If any of these things are
        !           225:         * different between the previous & current datagram, we send the
        !           226:         * current datagram `uncompressed'.
        !           227:         */
        !           228:        oth = (struct tcphdr *)&((int *)&cs->cs_ip)[hlen];
        !           229:        deltaS = hlen;
        !           230:        hlen += th->th_off;
        !           231:        hlen <<= 2;
        !           232: 
        !           233:        if (((u_short *)ip)[0] != ((u_short *)&cs->cs_ip)[0] ||
        !           234:            ((u_short *)ip)[3] != ((u_short *)&cs->cs_ip)[3] ||
        !           235:            ((u_short *)ip)[4] != ((u_short *)&cs->cs_ip)[4] ||
        !           236:            th->th_off != oth->th_off ||
        !           237:            (deltaS > 5 &&
        !           238:             BCMP(ip + 1, &cs->cs_ip + 1, (deltaS - 5) << 2)) ||
        !           239:            (th->th_off > 5 &&
        !           240:             BCMP(th + 1, oth + 1, (th->th_off - 5) << 2)))
        !           241:                goto uncompressed;
        !           242: 
        !           243:        /*
        !           244:         * Figure out which of the changing fields changed.  The
        !           245:         * receiver expects changes in the order: urgent, window,
        !           246:         * ack, seq (the order minimizes the number of temporaries
        !           247:         * needed in this section of code).
        !           248:         */
        !           249:        if (th->th_flags & TH_URG) {
        !           250:                deltaS = ntohs(th->th_urp);
        !           251:                ENCODEZ(deltaS);
        !           252:                changes |= NEW_U;
        !           253:        } else if (th->th_urp != oth->th_urp)
        !           254:                /* argh! URG not set but urp changed -- a sensible
        !           255:                 * implementation should never do this but RFC793
        !           256:                 * doesn't prohibit the change so we have to deal
        !           257:                 * with it. */
        !           258:                 goto uncompressed;
        !           259: 
        !           260:        if (deltaS = (u_short)(ntohs(th->th_win) - ntohs(oth->th_win))) {
        !           261:                ENCODE(deltaS);
        !           262:                changes |= NEW_W;
        !           263:        }
        !           264: 
        !           265:        if (deltaA = ntohl(th->th_ack) - ntohl(oth->th_ack)) {
        !           266:                if (deltaA > 0xffff)
        !           267:                        goto uncompressed;
        !           268:                ENCODE(deltaA);
        !           269:                changes |= NEW_A;
        !           270:        }
        !           271: 
        !           272:        if (deltaS = ntohl(th->th_seq) - ntohl(oth->th_seq)) {
        !           273:                if (deltaS > 0xffff)
        !           274:                        goto uncompressed;
        !           275:                ENCODE(deltaS);
        !           276:                changes |= NEW_S;
        !           277:        }
        !           278: 
        !           279:        switch(changes) {
        !           280: 
        !           281:        case 0:
        !           282:                /*
        !           283:                 * Nothing changed. If this packet contains data and the
        !           284:                 * last one didn't, this is probably a data packet following
        !           285:                 * an ack (normal on an interactive connection) and we send
        !           286:                 * it compressed.  Otherwise it's probably a retransmit,
        !           287:                 * retransmitted ack or window probe.  Send it uncompressed
        !           288:                 * in case the other side missed the compressed version.
        !           289:                 */
        !           290:                if (ip->ip_len != cs->cs_ip.ip_len &&
        !           291:                    ntohs(cs->cs_ip.ip_len) == hlen)
        !           292:                        break;
        !           293: 
        !           294:                /* (fall through) */
        !           295: 
        !           296:        case SPECIAL_I:
        !           297:        case SPECIAL_D:
        !           298:                /*
        !           299:                 * actual changes match one of our special case encodings --
        !           300:                 * send packet uncompressed.
        !           301:                 */
        !           302:                goto uncompressed;
        !           303: 
        !           304:        case NEW_S|NEW_A:
        !           305:                if (deltaS == deltaA &&
        !           306:                    deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
        !           307:                        /* special case for echoed terminal traffic */
        !           308:                        changes = SPECIAL_I;
        !           309:                        cp = new_seq;
        !           310:                }
        !           311:                break;
        !           312: 
        !           313:        case NEW_S:
        !           314:                if (deltaS == ntohs(cs->cs_ip.ip_len) - hlen) {
        !           315:                        /* special case for data xfer */
        !           316:                        changes = SPECIAL_D;
        !           317:                        cp = new_seq;
        !           318:                }
        !           319:                break;
        !           320:        }
        !           321: 
        !           322:        deltaS = ntohs(ip->ip_id) - ntohs(cs->cs_ip.ip_id);
        !           323:        if (deltaS != 1) {
        !           324:                ENCODEZ(deltaS);
        !           325:                changes |= NEW_I;
        !           326:        }
        !           327:        if (th->th_flags & TH_PUSH)
        !           328:                changes |= TCP_PUSH_BIT;
        !           329:        /*
        !           330:         * Grab the cksum before we overwrite it below.  Then update our
        !           331:         * state with this packet's header.
        !           332:         */
        !           333:        deltaA = ntohs(th->th_sum);
        !           334:        BCOPY(ip, &cs->cs_ip, hlen);
        !           335: 
        !           336:        /*
        !           337:         * We want to use the original packet as our compressed packet.
        !           338:         * (cp - new_seq) is the number of bytes we need for compressed
        !           339:         * sequence numbers.  In addition we need one byte for the change
        !           340:         * mask, one for the connection id and two for the tcp checksum.
        !           341:         * So, (cp - new_seq) + 4 bytes of header are needed.  hlen is how
        !           342:         * many bytes of the original packet to toss so subtract the two to
        !           343:         * get the new packet size.
        !           344:         */
        !           345:        deltaS = cp - new_seq;
        !           346:        cp = (u_char *)ip;
        !           347:        if (compress_cid == 0 || comp->last_xmit != cs->cs_id) {
        !           348:                comp->last_xmit = cs->cs_id;
        !           349:                hlen -= deltaS + 4;
        !           350:                cp += hlen;
        !           351:                *cp++ = changes | NEW_C;
        !           352:                *cp++ = cs->cs_id;
        !           353:        } else {
        !           354:                hlen -= deltaS + 3;
        !           355:                cp += hlen;
        !           356:                *cp++ = changes;
        !           357:        }
        !           358:        m->m_len -= hlen;
        !           359:        m->m_data += hlen;
        !           360:        *cp++ = deltaA >> 8;
        !           361:        *cp++ = deltaA;
        !           362:        BCOPY(new_seq, cp, deltaS);
        !           363:        INCR(sls_compressed)
        !           364:        return (TYPE_COMPRESSED_TCP);
        !           365: 
        !           366:        /*
        !           367:         * Update connection state cs & send uncompressed packet ('uncompressed'
        !           368:         * means a regular ip/tcp packet but with the 'conversation id' we hope
        !           369:         * to use on future compressed packets in the protocol field).
        !           370:         */
        !           371: uncompressed:
        !           372:        BCOPY(ip, &cs->cs_ip, hlen);
        !           373:        ip->ip_p = cs->cs_id;
        !           374:        comp->last_xmit = cs->cs_id;
        !           375:        return (TYPE_UNCOMPRESSED_TCP);
        !           376: }
        !           377: 
        !           378: 
        !           379: int
        !           380: sl_uncompress_tcp(bufp, len, type, comp)
        !           381:        u_char **bufp;
        !           382:        int len;
        !           383:        u_int type;
        !           384:        struct slcompress *comp;
        !           385: {
        !           386:        register u_char *cp;
        !           387:        register u_int hlen, changes;
        !           388:        register struct tcphdr *th;
        !           389:        register struct cstate *cs;
        !           390:        register struct ip *ip;
        !           391: 
        !           392:        switch (type) {
        !           393: 
        !           394:        case TYPE_UNCOMPRESSED_TCP:
        !           395:                ip = (struct ip *) *bufp;
        !           396:                if (ip->ip_p >= MAX_STATES)
        !           397:                        goto bad;
        !           398:                cs = &comp->rstate[comp->last_recv = ip->ip_p];
        !           399:                comp->flags &=~ SLF_TOSS;
        !           400:                ip->ip_p = IPPROTO_TCP;
        !           401:                hlen = ip->ip_hl;
        !           402:                hlen += ((struct tcphdr *)&((int *)ip)[hlen])->th_off;
        !           403:                hlen <<= 2;
        !           404:                BCOPY(ip, &cs->cs_ip, hlen);
        !           405:                cs->cs_ip.ip_sum = 0;
        !           406:                cs->cs_hlen = hlen;
        !           407:                INCR(sls_uncompressedin)
        !           408:                return (len);
        !           409: 
        !           410:        default:
        !           411:                goto bad;
        !           412: 
        !           413:        case TYPE_COMPRESSED_TCP:
        !           414:                break;
        !           415:        }
        !           416:        /* We've got a compressed packet. */
        !           417:        INCR(sls_compressedin)
        !           418:        cp = *bufp;
        !           419:        changes = *cp++;
        !           420:        if (changes & NEW_C) {
        !           421:                /* Make sure the state index is in range, then grab the state.
        !           422:                 * If we have a good state index, clear the 'discard' flag. */
        !           423:                if (*cp >= MAX_STATES)
        !           424:                        goto bad;
        !           425: 
        !           426:                comp->flags &=~ SLF_TOSS;
        !           427:                comp->last_recv = *cp++;
        !           428:        } else {
        !           429:                /* this packet has an implicit state index.  If we've
        !           430:                 * had a line error since the last time we got an
        !           431:                 * explicit state index, we have to toss the packet. */
        !           432:                if (comp->flags & SLF_TOSS) {
        !           433:                        INCR(sls_tossed)
        !           434:                        return (0);
        !           435:                }
        !           436:        }
        !           437:        cs = &comp->rstate[comp->last_recv];
        !           438:        hlen = cs->cs_ip.ip_hl << 2;
        !           439:        th = (struct tcphdr *)&((u_char *)&cs->cs_ip)[hlen];
        !           440:        th->th_sum = htons((*cp << 8) | cp[1]);
        !           441:        cp += 2;
        !           442:        if (changes & TCP_PUSH_BIT)
        !           443:                th->th_flags |= TH_PUSH;
        !           444:        else
        !           445:                th->th_flags &=~ TH_PUSH;
        !           446: 
        !           447:        switch (changes & SPECIALS_MASK) {
        !           448:        case SPECIAL_I:
        !           449:                {
        !           450:                register u_int i = ntohs(cs->cs_ip.ip_len) - cs->cs_hlen;
        !           451:                th->th_ack = htonl(ntohl(th->th_ack) + i);
        !           452:                th->th_seq = htonl(ntohl(th->th_seq) + i);
        !           453:                }
        !           454:                break;
        !           455: 
        !           456:        case SPECIAL_D:
        !           457:                th->th_seq = htonl(ntohl(th->th_seq) + ntohs(cs->cs_ip.ip_len)
        !           458:                                   - cs->cs_hlen);
        !           459:                break;
        !           460: 
        !           461:        default:
        !           462:                if (changes & NEW_U) {
        !           463:                        th->th_flags |= TH_URG;
        !           464:                        DECODEU(th->th_urp)
        !           465:                } else
        !           466:                        th->th_flags &=~ TH_URG;
        !           467:                if (changes & NEW_W)
        !           468:                        DECODES(th->th_win)
        !           469:                if (changes & NEW_A)
        !           470:                        DECODEL(th->th_ack)
        !           471:                if (changes & NEW_S)
        !           472:                        DECODEL(th->th_seq)
        !           473:                break;
        !           474:        }
        !           475:        if (changes & NEW_I) {
        !           476:                DECODES(cs->cs_ip.ip_id)
        !           477:        } else
        !           478:                cs->cs_ip.ip_id = htons(ntohs(cs->cs_ip.ip_id) + 1);
        !           479: 
        !           480:        /*
        !           481:         * At this point, cp points to the first byte of data in the
        !           482:         * packet.  If we're not aligned on a 4-byte boundary, copy the
        !           483:         * data down so the ip & tcp headers will be aligned.  Then back up
        !           484:         * cp by the tcp/ip header length to make room for the reconstructed
        !           485:         * header (we assume the packet we were handed has enough space to
        !           486:         * prepend 128 bytes of header).  Adjust the length to account for
        !           487:         * the new header & fill in the IP total length.
        !           488:         */
        !           489:        len -= (cp - *bufp);
        !           490:        if (len < 0)
        !           491:                /* we must have dropped some characters (crc should detect
        !           492:                 * this but the old slip framing won't) */
        !           493:                goto bad;
        !           494: 
        !           495:        if ((int)cp & 3) {
        !           496:                if (len > 0)
        !           497:                        (void) ovbcopy(cp, (caddr_t)((int)cp &~ 3), len);
        !           498:                cp = (u_char *)((int)cp &~ 3);
        !           499:        }
        !           500:        cp -= cs->cs_hlen;
        !           501:        len += cs->cs_hlen;
        !           502:        cs->cs_ip.ip_len = htons(len);
        !           503:        BCOPY(&cs->cs_ip, cp, cs->cs_hlen);
        !           504:        *bufp = cp;
        !           505: 
        !           506:        /* recompute the ip header checksum */
        !           507:        {
        !           508:                register u_short *bp = (u_short *)cp;
        !           509:                for (changes = 0; hlen > 0; hlen -= 2)
        !           510:                        changes += *bp++;
        !           511:                changes = (changes & 0xffff) + (changes >> 16);
        !           512:                changes = (changes & 0xffff) + (changes >> 16);
        !           513:                ((struct ip *)cp)->ip_sum = ~ changes;
        !           514:        }
        !           515:        return (len);
        !           516: bad:
        !           517:        comp->flags |= SLF_TOSS;
        !           518:        INCR(sls_errorin)
        !           519:        return (0);
        !           520: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.