0a7bd7a3b7fb4e81e30296672c5c9917867a7392
[akaros.git] / kern / src / net / compress.c
1 #include        "u.h"
2 #include        "../port/lib.h"
3 #include        "mem.h"
4 #include        "dat.h"
5 #include        "fns.h"
6 #include        "../port/error.h"
7
8 #include        "ip.h"
9 #include        "ppp.h"
10
11 typedef struct Iphdr    Iphdr;
12 typedef struct Tcphdr   Tcphdr;
13 typedef struct Ilhdr    Ilhdr;
14 typedef struct Hdr      Hdr;
15 typedef struct Tcpc     Tcpc;
16
17 struct Iphdr
18 {
19         uchar   vihl;           /* Version and header length */
20         uchar   tos;            /* Type of service */
21         uchar   length[2];      /* packet length */
22         uchar   id[2];          /* Identification */
23         uchar   frag[2];        /* Fragment information */
24         uchar   ttl;            /* Time to live */
25         uchar   proto;          /* Protocol */
26         uchar   cksum[2];       /* Header checksum */
27         ulong   src;            /* Ip source (byte ordering unimportant) */
28         ulong   dst;            /* Ip destination (byte ordering unimportant) */
29 };
30
31 struct Tcphdr
32 {
33         ulong   ports;          /* defined as a ulong to make comparisons easier */
34         uchar   seq[4];
35         uchar   ack[4];
36         uchar   flag[2];
37         uchar   win[2];
38         uchar   cksum[2];
39         uchar   urg[2];
40 };
41
42 struct Ilhdr
43 {
44         uchar   sum[2]; /* Checksum including header */
45         uchar   len[2]; /* Packet length */
46         uchar   type;           /* Packet type */
47         uchar   spec;           /* Special */
48         uchar   src[2]; /* Src port */
49         uchar   dst[2]; /* Dst port */
50         uchar   id[4];  /* Sequence id */
51         uchar   ack[4]; /* Acked sequence */
52 };
53
54 enum
55 {
56         URG             = 0x20,         /* Data marked urgent */
57         ACK             = 0x10,         /* Aknowledge is valid */
58         PSH             = 0x08,         /* Whole data pipe is pushed */
59         RST             = 0x04,         /* Reset connection */
60         SYN             = 0x02,         /* Pkt. is synchronise */
61         FIN             = 0x01,         /* Start close down */
62
63         IP_DF           = 0x4000,       /* Don't fragment */
64
65         IP_TCPPROTO     = 6,
66         IP_ILPROTO      = 40,
67         IL_IPHDR        = 20,
68 };
69
70 struct Hdr
71 {
72         uchar   buf[128];
73         Iphdr   *ip;
74         Tcphdr  *tcp;
75         int     len;
76 };
77
78 struct Tcpc
79 {
80         uchar   lastrecv;
81         uchar   lastxmit;
82         uchar   basexmit;
83         uchar   err;
84         uchar   compressid;
85         Hdr     t[MAX_STATES];
86         Hdr     r[MAX_STATES];
87 };
88
89 enum
90 {       /* flag bits for what changed in a packet */
91         NEW_U=(1<<0),   /* tcp only */
92         NEW_W=(1<<1),   /* tcp only */
93         NEW_A=(1<<2),   /* il tcp */
94         NEW_S=(1<<3),   /* tcp only */
95         NEW_P=(1<<4),   /* tcp only */
96         NEW_I=(1<<5),   /* il tcp */
97         NEW_C=(1<<6),   /* il tcp */
98         NEW_T=(1<<7),   /* il only */
99         TCP_PUSH_BIT    = 0x10,
100 };
101
102 /* reserved, special-case values of above for tcp */
103 #define SPECIAL_I (NEW_S|NEW_W|NEW_U)           /* echoed interactive traffic */
104 #define SPECIAL_D (NEW_S|NEW_A|NEW_W|NEW_U)     /* unidirectional data */
105 #define SPECIALS_MASK (NEW_S|NEW_A|NEW_W|NEW_U)
106
107 int
108 encode(void *p, ulong n)
109 {
110         uchar   *cp;
111
112         cp = p;
113         if(n >= 256 || n == 0) {
114                 *cp++ = 0;
115                 cp[0] = n >> 8;
116                 cp[1] = n;
117                 return 3;
118         } else 
119                 *cp = n;
120         return 1;
121 }
122
123 #define DECODEL(f) { \
124         if (*cp == 0) {\
125                 hnputl(f, nhgetl(f) + ((cp[1] << 8) | cp[2])); \
126                 cp += 3; \
127         } else { \
128                 hnputl(f, nhgetl(f) + (ulong)*cp++); \
129         } \
130 }
131 #define DECODES(f) { \
132         if (*cp == 0) {\
133                 hnputs(f, nhgets(f) + ((cp[1] << 8) | cp[2])); \
134                 cp += 3; \
135         } else { \
136                 hnputs(f, nhgets(f) + (ulong)*cp++); \
137         } \
138 }
139
140 ushort
141 tcpcompress(Tcpc *comp, Block *b, Fs *)
142 {
143         Iphdr   *ip;            /* current packet */
144         Tcphdr  *tcp;           /* current pkt */
145         ulong   iplen, tcplen, hlen;    /* header length in bytes */
146         ulong   deltaS, deltaA; /* general purpose temporaries */
147         ulong   changes;        /* change mask */
148         uchar   new_seq[16];    /* changes from last to current */
149         uchar   *cp;
150         Hdr     *h;             /* last packet */
151         int     i, j;
152
153         /*
154          * Bail if this is not a compressible TCP/IP packet
155          */
156         ip = (Iphdr*)b->rp;
157         iplen = (ip->vihl & 0xf) << 2;
158         tcp = (Tcphdr*)(b->rp + iplen);
159         tcplen = (tcp->flag[0] & 0xf0) >> 2;
160         hlen = iplen + tcplen;
161         if((tcp->flag[1] & (SYN|FIN|RST|ACK)) != ACK)
162                 return Pip;     /* connection control */
163
164         /*
165          * Packet is compressible, look for a connection
166          */
167         changes = 0;
168         cp = new_seq;
169         j = comp->lastxmit;
170         h = &comp->t[j];
171         if(ip->src != h->ip->src || ip->dst != h->ip->dst
172         || tcp->ports != h->tcp->ports) {
173                 for(i = 0; i < MAX_STATES; ++i) {
174                         j = (comp->basexmit + i) % MAX_STATES;
175                         h = &comp->t[j];
176                         if(ip->src == h->ip->src && ip->dst == h->ip->dst
177                         && tcp->ports == h->tcp->ports)
178                                 goto found;
179                 }
180
181                 /* no connection, reuse the oldest */
182                 if(i == MAX_STATES) {
183                         j = comp->basexmit;
184                         j = (j + MAX_STATES - 1) % MAX_STATES;
185                         comp->basexmit = j;
186                         h = &comp->t[j];
187                         goto raise;
188                 }
189         }
190 found:
191
192         /*
193          * Make sure that only what we expect to change changed. 
194          */
195         if(ip->vihl  != h->ip->vihl || ip->tos   != h->ip->tos ||
196            ip->ttl   != h->ip->ttl  || ip->proto != h->ip->proto)
197                 goto raise;     /* headers changed */
198         if(iplen != sizeof(Iphdr) && memcmp(ip+1, h->ip+1, iplen - sizeof(Iphdr)))
199                 goto raise;     /* ip options changed */
200         if(tcplen != sizeof(Tcphdr) && memcmp(tcp+1, h->tcp+1, tcplen - sizeof(Tcphdr)))
201                 goto raise;     /* tcp options changed */
202
203         if(tcp->flag[1] & URG) {
204                 cp += encode(cp, nhgets(tcp->urg));
205                 changes |= NEW_U;
206         } else if(memcmp(tcp->urg, h->tcp->urg, sizeof(tcp->urg)) != 0)
207                 goto raise;
208         if(deltaS = nhgets(tcp->win) - nhgets(h->tcp->win)) {
209                 cp += encode(cp, deltaS);
210                 changes |= NEW_W;
211         }
212         if(deltaA = nhgetl(tcp->ack) - nhgetl(h->tcp->ack)) {
213                 if(deltaA > 0xffff)
214                         goto raise;
215                 cp += encode(cp, deltaA);
216                 changes |= NEW_A;
217         }
218         if(deltaS = nhgetl(tcp->seq) - nhgetl(h->tcp->seq)) {
219                 if (deltaS > 0xffff)
220                         goto raise;
221                 cp += encode(cp, deltaS);
222                 changes |= NEW_S;
223         }
224
225         /*
226          * Look for the special-case encodings.
227          */
228         switch(changes) {
229         case 0:
230                 /*
231                  * Nothing changed. If this packet contains data and the last
232                  * one didn't, this is probably a data packet following an
233                  * ack (normal on an interactive connection) and we send it
234                  * compressed. Otherwise it's probably a retransmit,
235                  * retransmitted ack or window probe.  Send it uncompressed
236                  * in case the other side missed the compressed version.
237                  */
238                 if(nhgets(ip->length) == nhgets(h->ip->length) ||
239                    nhgets(h->ip->length) != hlen)
240                         goto raise;
241                 break;
242         case SPECIAL_I:
243         case SPECIAL_D:
244                 /*
245                  * Actual changes match one of our special case encodings --
246                  * send packet uncompressed.
247                  */
248                 goto raise;
249         case NEW_S | NEW_A:
250                 if (deltaS == deltaA &&
251                         deltaS == nhgets(h->ip->length) - hlen) {
252                         /* special case for echoed terminal traffic */
253                         changes = SPECIAL_I;
254                         cp = new_seq;
255                 }
256                 break;
257         case NEW_S:
258                 if (deltaS == nhgets(h->ip->length) - hlen) {
259                         /* special case for data xfer */
260                         changes = SPECIAL_D;
261                         cp = new_seq;
262                 }
263                 break;
264         }
265         deltaS = nhgets(ip->id) - nhgets(h->ip->id);
266         if(deltaS != 1) {
267                 cp += encode(cp, deltaS);
268                 changes |= NEW_I;
269         }
270         if (tcp->flag[1] & PSH)
271                 changes |= TCP_PUSH_BIT;
272         /*
273          * Grab the cksum before we overwrite it below. Then update our
274          * state with this packet's header.
275          */
276         deltaA = nhgets(tcp->cksum);
277         memmove(h->buf, b->rp, hlen);
278         h->len = hlen;
279         h->tcp = (Tcphdr*)(h->buf + iplen);
280
281         /*
282          * We want to use the original packet as our compressed packet. (cp -
283          * new_seq) is the number of bytes we need for compressed sequence
284          * numbers. In addition we need one byte for the change mask, one
285          * for the connection id and two for the tcp checksum. So, (cp -
286          * new_seq) + 4 bytes of header are needed. hlen is how many bytes
287          * of the original packet to toss so subtract the two to get the new
288          * packet size. The temporaries are gross -egs.
289          */
290         deltaS = cp - new_seq;
291         cp = b->rp;
292         if(comp->lastxmit != j || comp->compressid == 0) {
293                 comp->lastxmit = j;
294                 hlen -= deltaS + 4;
295                 cp += hlen;
296                 *cp++ = (changes | NEW_C);
297                 *cp++ = j;
298         } else {
299                 hlen -= deltaS + 3;
300                 cp += hlen;
301                 *cp++ = changes;
302         }
303         b->rp += hlen;
304         hnputs(cp, deltaA);
305         cp += 2;
306         memmove(cp, new_seq, deltaS);
307         return Pvjctcp;
308
309 raise:
310         /*
311          * Update connection state & send uncompressed packet
312          */
313         memmove(h->buf, b->rp, hlen);
314         h->tcp = (Tcphdr*)(h->buf + iplen);
315         h->len = hlen;
316         h->ip->proto = j;
317         comp->lastxmit = j;
318         return Pvjutcp;
319 }
320
321 Block*
322 tcpuncompress(Tcpc *comp, Block *b, ushort type, Fs *f)
323 {
324         uchar   *cp, changes;
325         int     i;
326         int     iplen, len;
327         Iphdr   *ip;
328         Tcphdr  *tcp;
329         Hdr     *h;
330
331         if(type == Pvjutcp) {
332                 /*
333                  *  Locate the saved state for this connection. If the state
334                  *  index is legal, clear the 'discard' flag.
335                  */
336                 ip = (Iphdr*)b->rp;
337                 if(ip->proto >= MAX_STATES)
338                         goto raise;
339                 iplen = (ip->vihl & 0xf) << 2;
340                 tcp = (Tcphdr*)(b->rp + iplen);
341                 comp->lastrecv = ip->proto;
342                 len = iplen + ((tcp->flag[0] & 0xf0) >> 2);
343                 comp->err = 0;
344 netlog(f, Logcompress, "uncompressed %d\n", comp->lastrecv);
345                 /*
346                  * Restore the IP protocol field then save a copy of this
347                  * packet header. The checksum is zeroed in the copy so we
348                  * don't have to zero it each time we process a compressed
349                  * packet.
350                  */
351                 ip->proto = IP_TCPPROTO;
352                 h = &comp->r[comp->lastrecv];
353                 memmove(h->buf, b->rp, len);
354                 h->tcp = (Tcphdr*)(h->buf + iplen);
355                 h->len = len;
356                 h->ip->cksum[0] = h->ip->cksum[1] = 0;
357                 return b;
358         }
359
360         cp = b->rp;
361         changes = *cp++;
362         if(changes & NEW_C) {
363                 /*
364                  * Make sure the state index is in range, then grab the
365                  * state. If we have a good state index, clear the 'discard'
366                  * flag.
367                  */
368                 if(*cp >= MAX_STATES)
369                         goto raise;
370                 comp->err = 0;
371                 comp->lastrecv = *cp++;
372 netlog(f, Logcompress, "newc %d\n", comp->lastrecv);
373         } else {
374                 /*
375                  * This packet has no state index. If we've had a
376                  * line error since the last time we got an explicit state
377                  * index, we have to toss the packet.
378                  */
379                 if(comp->err != 0){
380                         freeblist(b);
381                         return nil;
382                 }
383 netlog(f, Logcompress, "oldc %d\n", comp->lastrecv);
384         }
385
386         /*
387          * Find the state then fill in the TCP checksum and PUSH bit.
388          */
389         h = &comp->r[comp->lastrecv];
390         ip = h->ip;
391         tcp = h->tcp;
392         len = h->len;
393         memmove(tcp->cksum, cp, sizeof tcp->cksum);
394         cp += 2;
395         if(changes & TCP_PUSH_BIT)
396                 tcp->flag[1] |= PSH;
397         else
398                 tcp->flag[1] &= ~PSH;
399         /*
400          * Fix up the state's ack, seq, urg and win fields based on the
401          * changemask.
402          */
403         switch (changes & SPECIALS_MASK) {
404         case SPECIAL_I:
405                 i = nhgets(ip->length) - len;
406                 hnputl(tcp->ack, nhgetl(tcp->ack) + i);
407                 hnputl(tcp->seq, nhgetl(tcp->seq) + i);
408                 break;
409
410         case SPECIAL_D:
411                 hnputl(tcp->seq, nhgetl(tcp->seq) + nhgets(ip->length) - len);
412                 break;
413
414         default:
415                 if(changes & NEW_U) {
416                         tcp->flag[1] |= URG;
417                         if(*cp == 0){
418                                 hnputs(tcp->urg, nhgets(cp+1));
419                                 cp += 3;
420                         }else
421                                 hnputs(tcp->urg, *cp++);
422                 } else
423                         tcp->flag[1] &= ~URG;
424                 if(changes & NEW_W)
425                         DECODES(tcp->win)
426                 if(changes & NEW_A)
427                         DECODEL(tcp->ack)
428                 if(changes & NEW_S)
429                         DECODEL(tcp->seq)
430                 break;
431         }
432
433         /* Update the IP ID */
434         if(changes & NEW_I)
435                 DECODES(ip->id)
436         else
437                 hnputs(ip->id, nhgets(ip->id) + 1);
438
439         /*
440          *  At this point, cp points to the first byte of data in the packet.
441          *  Back up cp by the TCP/IP header length to make room for the
442          *  reconstructed header.
443          *  We assume the packet we were handed has enough space to prepend
444          *  up to 128 bytes of header.
445          */
446         b->rp = cp;
447         if(b->rp - b->base < len){
448                 b = padblock(b, len);
449                 b = pullupblock(b, blocklen(b));
450         } else
451                 b->rp -= len;
452         hnputs(ip->length, BLEN(b));
453         memmove(b->rp, ip, len);
454         
455         /* recompute the ip header checksum */
456         ip = (Iphdr*)b->rp;
457         hnputs(ip->cksum, ipcsum(b->rp));
458         return b;
459
460 raise:
461         netlog(f, Logcompress, "Bad Packet!\n");
462         comp->err = 1;
463         freeblist(b);
464         return nil;
465 }
466
467 Tcpc*
468 compress_init(Tcpc *c)
469 {
470         int i;
471         Hdr *h;
472
473         if(c == nil){
474                 c = malloc(sizeof(Tcpc));
475                 if(c == nil)
476                         return nil;
477         }
478         memset(c, 0, sizeof(*c));
479         for(i = 0; i < MAX_STATES; i++){
480                 h = &c->t[i];
481                 h->ip = (Iphdr*)h->buf;
482                 h->tcp = (Tcphdr*)(h->buf + 10);
483                 h->len = 20;
484                 h = &c->r[i];
485                 h->ip = (Iphdr*)h->buf;
486                 h->tcp = (Tcphdr*)(h->buf + 10);
487                 h->len = 20;
488         }
489
490         return c;
491 }
492
493 ushort
494 compress(Tcpc *tcp, Block *b, Fs *f)
495 {
496         Iphdr           *ip;
497
498         /*
499          * Bail if this is not a compressible IP packet
500          */
501         ip = (Iphdr*)b->rp;
502         if((nhgets(ip->frag) & 0x3fff) != 0)
503                 return Pip;
504
505         switch(ip->proto) {
506         case IP_TCPPROTO:
507                 return tcpcompress(tcp, b, f);
508         default:
509                 return Pip;
510         }
511 }
512
513 int
514 compress_negotiate(Tcpc *tcp, uchar *data)
515 {
516         if(data[0] != MAX_STATES - 1)
517                 return -1;
518         tcp->compressid = data[1];
519         return 0;
520 }