qio: Track the amount of bytes read
[akaros.git] / kern / src / net / ipaux.c
1 /* Copyright © 1994-1999 Lucent Technologies Inc.  All rights reserved.
2  * Portions Copyright © 1997-1999 Vita Nuova Limited
3  * Portions Copyright © 2000-2007 Vita Nuova Holdings Limited
4  *                                (www.vitanuova.com)
5  * Revisions Copyright © 2000-2007 Lucent Technologies Inc. and others
6  *
7  * Modified for the Akaros operating system:
8  * Copyright (c) 2013-2014 The Regents of the University of California
9  * Copyright (c) 2013-2015 Google Inc.
10  *
11  * Permission is hereby granted, free of charge, to any person obtaining a copy
12  * of this software and associated documentation files (the "Software"), to deal
13  * in the Software without restriction, including without limitation the rights
14  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
15  * copies of the Software, and to permit persons to whom the Software is
16  * furnished to do so, subject to the following conditions:
17  *
18  * The above copyright notice and this permission notice shall be included in
19  * all copies or substantial portions of the Software.
20  *
21  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
24  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
25  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
26  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
27  * SOFTWARE. */
28
29 #include <vfs.h>
30 #include <kfs.h>
31 #include <slab.h>
32 #include <kmalloc.h>
33 #include <kref.h>
34 #include <string.h>
35 #include <stdio.h>
36 #include <assert.h>
37 #include <error.h>
38 #include <cpio.h>
39 #include <pmap.h>
40 #include <smp.h>
41 #include <ip.h>
42 #include <endian.h>
43
44 /*
45  *  well known IP addresses
46  */
47 uint8_t IPv4_loopback[IPaddrlen] = {
48         0, 0, 0, 0,
49         0, 0, 0, 0,
50         0, 0, 0xff, 0xff,
51         0x7f, 0x00, 0x00, 0x01
52 };
53
54 uint8_t IPv4_zeroes[IPaddrlen] = {
55         0, 0, 0, 0,
56         0, 0, 0, 0,
57         0, 0, 0xff, 0xff,
58         0x00, 0x00, 0x00, 0x00
59 };
60
61 uint8_t IPv4bcast[IPaddrlen] = {
62         0, 0, 0, 0,
63         0, 0, 0, 0,
64         0, 0, 0xff, 0xff,
65         0xff, 0xff, 0xff, 0xff
66 };
67
68 uint8_t IPv4allsys[IPaddrlen] = {
69         0, 0, 0, 0,
70         0, 0, 0, 0,
71         0, 0, 0xff, 0xff,
72         0xe0, 0, 0, 0x01
73 };
74
75 uint8_t IPv4allrouter[IPaddrlen] = {
76         0, 0, 0, 0,
77         0, 0, 0, 0,
78         0, 0, 0xff, 0xff,
79         0xe0, 0, 0, 0x02
80 };
81
82 uint8_t IPallbits[IPaddrlen] = {
83         0xff, 0xff, 0xff, 0xff,
84         0xff, 0xff, 0xff, 0xff,
85         0xff, 0xff, 0xff, 0xff,
86         0xff, 0xff, 0xff, 0xff
87 };
88
89 uint8_t IPnoaddr[IPaddrlen];
90
91 /*
92  *  prefix of all v4 addresses
93  */
94 uint8_t v4prefix[IPaddrlen] = {
95         0, 0, 0, 0,
96         0, 0, 0, 0,
97         0, 0, 0xff, 0xff,
98         0, 0, 0, 0
99 };
100
101 char *v6hdrtypes[Maxhdrtype] = {
102         [HBH] "HopbyHop",
103         [ICMP] "ICMP",
104         [IGMP] "IGMP",
105         [GGP] "GGP",
106         [IPINIP] "IP",
107         [ST] "ST",
108         [TCP] "TCP",
109         [UDP] "UDP",
110         [ISO_TP4] "ISO_TP4",
111         [RH] "Routinghdr",
112         [FH] "Fraghdr",
113         [IDRP] "IDRP",
114         [RSVP] "RSVP",
115         [AH] "Authhdr",
116         [ESP] "ESP",
117         [ICMPv6] "ICMPv6",
118         [NNH] "Nonexthdr",
119         [ISO_IP] "ISO_IP",
120         [IGRP] "IGRP",
121         [OSPF] "OSPF",
122 };
123
124 /*
125  *  well known IPv6 addresses
126  */
127 uint8_t v6Unspecified[IPaddrlen] = {
128         0, 0, 0, 0,
129         0, 0, 0, 0,
130         0, 0, 0, 0,
131         0, 0, 0, 0
132 };
133
134 uint8_t v6loopback[IPaddrlen] = {
135         0, 0, 0, 0,
136         0, 0, 0, 0,
137         0, 0, 0, 0,
138         0, 0, 0, 0x01
139 };
140
141 uint8_t v6linklocal[IPaddrlen] = {
142         0xfe, 0x80, 0, 0,
143         0, 0, 0, 0,
144         0, 0, 0, 0,
145         0, 0, 0, 0
146 };
147
148 uint8_t v6linklocalmask[IPaddrlen] = {
149         0xff, 0xff, 0xff, 0xff,
150         0xff, 0xff, 0xff, 0xff,
151         0, 0, 0, 0,
152         0, 0, 0, 0
153 };
154
155 int v6llpreflen = 8;                    // link-local prefix length
156 uint8_t v6sitelocal[IPaddrlen] = {
157         0xfe, 0xc0, 0, 0,
158         0, 0, 0, 0,
159         0, 0, 0, 0,
160         0, 0, 0, 0
161 };
162
163 uint8_t v6sitelocalmask[IPaddrlen] = {
164         0xff, 0xff, 0xff, 0xff,
165         0xff, 0xff, 0xff, 0xff,
166         0, 0, 0, 0,
167         0, 0, 0, 0
168 };
169
170 int v6slpreflen = 6;                    // site-local prefix length
171 uint8_t v6glunicast[IPaddrlen] = {
172         0x08, 0, 0, 0,
173         0, 0, 0, 0,
174         0, 0, 0, 0,
175         0, 0, 0, 0
176 };
177
178 uint8_t v6multicast[IPaddrlen] = {
179         0xff, 0, 0, 0,
180         0, 0, 0, 0,
181         0, 0, 0, 0,
182         0, 0, 0, 0
183 };
184
185 uint8_t v6multicastmask[IPaddrlen] = {
186         0xff, 0, 0, 0,
187         0, 0, 0, 0,
188         0, 0, 0, 0,
189         0, 0, 0, 0
190 };
191
192 int v6mcpreflen = 1;                    // multicast prefix length
193 uint8_t v6allnodesN[IPaddrlen] = {
194         0xff, 0x01, 0, 0,
195         0, 0, 0, 0,
196         0, 0, 0, 0,
197         0, 0, 0, 0x01
198 };
199
200 uint8_t v6allnodesNmask[IPaddrlen] = {
201         0xff, 0xff, 0, 0,
202         0, 0, 0, 0,
203         0, 0, 0, 0,
204         0, 0, 0, 0
205 };
206
207 int v6aNpreflen = 2;                    // all nodes (N) prefix
208 uint8_t v6allnodesL[IPaddrlen] = {
209         0xff, 0x02, 0, 0,
210         0, 0, 0, 0,
211         0, 0, 0, 0,
212         0, 0, 0, 0x01
213 };
214
215 uint8_t v6allnodesLmask[IPaddrlen] = {
216         0xff, 0xff, 0, 0,
217         0, 0, 0, 0,
218         0, 0, 0, 0,
219         0, 0, 0, 0
220 };
221
222 int v6aLpreflen = 2;                    // all nodes (L) prefix
223 uint8_t v6allroutersN[IPaddrlen] = {
224         0xff, 0x01, 0, 0,
225         0, 0, 0, 0,
226         0, 0, 0, 0,
227         0, 0, 0, 0x02
228 };
229
230 uint8_t v6allroutersL[IPaddrlen] = {
231         0xff, 0x02, 0, 0,
232         0, 0, 0, 0,
233         0, 0, 0, 0,
234         0, 0, 0, 0x02
235 };
236
237 uint8_t v6allroutersS[IPaddrlen] = {
238         0xff, 0x05, 0, 0,
239         0, 0, 0, 0,
240         0, 0, 0, 0,
241         0, 0, 0, 0x02
242 };
243
244 uint8_t v6solicitednode[IPaddrlen] = {
245         0xff, 0x02, 0, 0,
246         0, 0, 0, 0,
247         0, 0, 0, 0x01,
248         0xff, 0, 0, 0
249 };
250
251 uint8_t v6solicitednodemask[IPaddrlen] = {
252         0xff, 0xff, 0xff, 0xff,
253         0xff, 0xff, 0xff, 0xff,
254         0xff, 0xff, 0xff, 0xff,
255         0xff, 0x0, 0x0, 0x0
256 };
257
258 int v6snpreflen = 13;
259
260 uint16_t ptclcsum_one(struct block *bp, int offset, int len)
261 {
262         uint8_t *addr;
263         uint32_t losum, hisum;
264         uint16_t csum;
265         int odd, blocklen, x, i, boff;
266         struct extra_bdata *ebd;
267
268         hisum = 0;
269         losum = 0;
270         odd = 0;
271
272         if (offset < BHLEN(bp)) {
273                 x = MIN(len, BHLEN(bp) - offset);
274                 odd = (odd + x) & 1;
275                 addr = bp->rp + offset;
276                 losum = ptclbsum(addr, x);
277                 len -= x;
278                 offset = 0;
279         } else {
280                 offset -= BHLEN(bp);
281         }
282         for (int i = 0; (i < bp->nr_extra_bufs) && len; i++) {
283                 ebd = &bp->extra_data[i];
284                 boff = MIN(offset, ebd->len);
285                 if (offset) {
286                         offset -= boff;
287                         if (offset)
288                                 continue;
289                 }
290                 x = MIN(len, ebd->len - boff);
291                 addr = (void *)(ebd->base + ebd->off);
292                 if (odd)
293                         hisum += ptclbsum(addr, x);
294                 else
295                         losum += ptclbsum(addr, x);
296                 odd = (odd + x) & 1;
297                 len -= x;
298         }
299         losum += hisum >> 8;
300         losum += (hisum & 0xff) << 8;
301         while ((csum = losum >> 16) != 0)
302                 losum = csum + (losum & 0xffff);
303
304         return losum & 0xffff;
305 }
306
307 uint16_t ptclcsum(struct block *bp, int offset, int len)
308 {
309         uint8_t *addr;
310         uint32_t losum, hisum;
311         uint16_t csum;
312         int odd, blocklen, x;
313
314         /* Correct to front of data area */
315         while (bp != NULL && offset && offset >= BLEN(bp)) {
316                 offset -= BLEN(bp);
317                 bp = bp->next;
318         }
319         if (bp == NULL)
320                 return 0;
321
322         addr = bp->rp + offset;
323         blocklen = BLEN(bp) - offset;
324
325         if (bp->next == NULL && bp->extra_len == 0) {
326                 if (blocklen < len)
327                         len = blocklen;
328                 return ~ptclbsum(addr, len) & 0xffff;
329         }
330
331         losum = 0;
332         hisum = 0;
333
334         odd = 0;
335         while (len) {
336                 x = MIN(blocklen, len);
337                 csum = ptclcsum_one(bp, offset, x);
338                 if (odd)
339                         hisum += csum;
340                 else
341                         losum += csum;
342                 odd = (odd + x) & 1;
343                 len -= x;
344
345                 bp = bp->next;
346                 if (bp == NULL)
347                         break;
348                 blocklen = BLEN(bp);
349                 offset = 0;
350         }
351
352         losum += hisum >> 8;
353         losum += (hisum & 0xff) << 8;
354         while ((csum = losum >> 16) != 0)
355                 losum = csum + (losum & 0xffff);
356
357         return ~losum & 0xffff;
358 }
359
360 enum {
361         Isprefix = 16,
362 };
363
364 static uint8_t prefixvals[256] = {
365         [0x00] 0 | Isprefix,
366         [0x80] 1 | Isprefix,
367         [0xC0] 2 | Isprefix,
368         [0xE0] 3 | Isprefix,
369         [0xF0] 4 | Isprefix,
370         [0xF8] 5 | Isprefix,
371         [0xFC] 6 | Isprefix,
372         [0xFE] 7 | Isprefix,
373         [0xFF] 8 | Isprefix,
374 };
375
376 #define CLASS(p) ((*( uint8_t *)(p))>>6)
377
378 extern char *v4parseip(uint8_t * to, char *from)
379 {
380         int i;
381         char *p;
382
383         p = from;
384         for (i = 0; i < 4 && *p; i++) {
385                 to[i] = strtoul(p, &p, 0);
386                 if (*p == '.')
387                         p++;
388         }
389         switch (CLASS(to)) {
390                 case 0: /* class A - 1 uint8_t net */
391                 case 1:
392                         if (i == 3) {
393                                 to[3] = to[2];
394                                 to[2] = to[1];
395                                 to[1] = 0;
396                         } else if (i == 2) {
397                                 to[3] = to[1];
398                                 to[1] = 0;
399                         }
400                         break;
401                 case 2: /* class B - 2 uint8_t net */
402                         if (i == 3) {
403                                 to[3] = to[2];
404                                 to[2] = 0;
405                         }
406                         break;
407         }
408         return p;
409 }
410
411 int isv4(uint8_t * ip)
412 {
413         unsigned short *ips = (unsigned short *)ip;
414         return 0xffff == ips[5];
415 }
416
417 /*
418  *  the following routines are unrolled with no memset's to speed
419  *  up the usual case.  They assume IP addresses are naturally aligned.
420  */
421 void v4tov6(uint8_t * v6, uint8_t * v4)
422 {
423         uint32_t *v6p = (uint32_t *)v6;
424         uint32_t *v4p = (uint32_t *)v4;
425
426         v6p[0] = 0;
427         v6p[1] = 0;
428         v6p[2] = (unsigned int)PP_NTOHL(0xffff);
429         v6p[3] = v4p[0];
430 }
431
432 int v6tov4(uint8_t * v4, uint8_t * v6)
433 {
434
435         uint32_t *v6p = (uint32_t *)v6;
436         uint32_t *v4p = (uint32_t *)v4;
437
438         if (v6p[0] == 0 && v6p[1] == 0 &&
439             v6p[2] == (unsigned int)PP_NTOHL(0xffff)) {
440                 v4p[0] = v6p[3];
441                 return 0;
442         } else {
443                 v4p[0] = 0;
444                 return -1;
445         }
446 }
447
448 uint32_t parseip(uint8_t * to, char *from)
449 {
450         int i, elipsis = 0, v4 = 1;
451         uint32_t x;
452         char *p, *op;
453
454         memset(to, 0, IPaddrlen);
455         p = from;
456         for (i = 0; i < 16 && *p; i += 2) {
457                 op = p;
458                 x = strtoul(p, &p, 16);
459                 if (*p == '.' || (*p == 0 && i == 0)) {
460                         p = v4parseip(to + i, op);
461                         i += 4;
462                         break;
463                 } else {
464                         to[i] = x >> 8;
465                         to[i + 1] = x;
466                 }
467                 if (*p == ':') {
468                         v4 = 0;
469                         if (*++p == ':') {
470                                 elipsis = i + 2;
471                                 p++;
472                         }
473                 }
474         }
475         if (i < 16) {
476                 memmove(&to[elipsis + 16 - i], &to[elipsis], i - elipsis);
477                 memset(&to[elipsis], 0, 16 - i);
478         }
479         if (v4) {
480                 to[10] = to[11] = 0xff;
481                 return nhgetl(to + 12);
482         } else
483                 return 6;
484 }
485
486 /*
487  *  hack to allow ip v4 masks to be entered in the old
488  *  style
489  */
490 uint32_t parseipmask(uint8_t * to, char *from)
491 {
492         uint32_t x;
493         int i;
494         uint8_t *p;
495
496         if (*from == '/') {
497                 /* as a number of prefix bits */
498                 i = atoi(from + 1);
499                 if (i < 0)
500                         i = 0;
501                 if (i > 128)
502                         i = 128;
503                 memset(to, 0, IPaddrlen);
504                 for (p = to; i >= 8; i -= 8)
505                         *p++ = 0xff;
506                 if (i > 0)
507                         *p = ~((1 << (8 - i)) - 1);
508                 x = nhgetl(to + IPv4off);
509         } else {
510                 /* as a straight bit mask */
511                 x = parseip(to, from);
512                 if (memcmp(to, v4prefix, IPv4off) == 0)
513                         memset(to, 0xff, IPv4off);
514         }
515         return x;
516 }
517
518 void maskip(uint8_t * from, uint8_t * mask, uint8_t * to)
519 {
520         int i;
521
522         for (i = 0; i < IPaddrlen; i++)
523                 to[i] = from[i] & mask[i];
524 }
525
526 uint8_t classmask[4][16] = {
527         {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
528          0xff, 0x00, 0x00, 0x00}
529         ,
530         {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
531          0xff, 0x00, 0x00, 0x00}
532         ,
533         {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
534          0xff, 0xff, 0x00, 0x00}
535         ,
536
537         {0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
538          0xff, 0xff, 0xff, 0x00}
539         ,
540 };
541
542 uint8_t *defmask(uint8_t * ip)
543 {
544         if (isv4(ip))
545                 return classmask[ip[IPv4off] >> 6];
546         else {
547                 if (ipcmp(ip, v6loopback) == 0)
548                         return IPallbits;
549                 else if (memcmp(ip, v6linklocal, v6llpreflen) == 0)
550                         return v6linklocalmask;
551                 else if (memcmp(ip, v6sitelocal, v6slpreflen) == 0)
552                         return v6sitelocalmask;
553                 else if (memcmp(ip, v6solicitednode, v6snpreflen) == 0)
554                         return v6solicitednodemask;
555                 else if (memcmp(ip, v6multicast, v6mcpreflen) == 0)
556                         return v6multicastmask;
557                 return IPallbits;
558         }
559 }
560
561 void ipv62smcast(uint8_t * smcast, uint8_t * a)
562 {
563         assert(IPaddrlen == 16);
564         memmove(smcast, v6solicitednode, IPaddrlen);
565         smcast[13] = a[13];
566         smcast[14] = a[14];
567         smcast[15] = a[15];
568 }
569
570 /*
571  *  parse a hex mac address
572  */
573 int parsemac(uint8_t * to, char *from, int len)
574 {
575         char nip[4];
576         char *p;
577         int i;
578
579         p = from;
580         memset(to, 0, len);
581         for (i = 0; i < len; i++) {
582                 if (p[0] == '\0' || p[1] == '\0')
583                         break;
584
585                 nip[0] = p[0];
586                 nip[1] = p[1];
587                 nip[2] = '\0';
588                 p += 2;
589
590                 to[i] = strtoul(nip, 0, 16);
591                 if (*p == ':')
592                         p++;
593         }
594         return i;
595 }
596
597 /*
598  *  hashing tcp, udp, ... connections
599  *  gcc weirdness: it gave a bogus result until ron split the %= out.
600  */
601 uint32_t iphash(uint8_t * sa, uint16_t sp, uint8_t * da, uint16_t dp)
602 {
603         uint32_t ret;
604         ret = (sa[IPaddrlen - 1] << 24) ^ (sp << 16) ^ (da[IPaddrlen - 1] << 8)
605                 ^ dp;
606         ret %= Nhash;
607         return ret;
608 }
609
610 void iphtadd(struct Ipht *ht, struct conv *c)
611 {
612         uint32_t hv;
613         struct Iphash *h;
614
615         hv = iphash(c->raddr, c->rport, c->laddr, c->lport);
616         h = kzmalloc(sizeof(*h), 0);
617         if (ipcmp(c->raddr, IPnoaddr) != 0)
618                 h->match = IPmatchexact;
619         else {
620                 if (ipcmp(c->laddr, IPnoaddr) != 0) {
621                         if (c->lport == 0)
622                                 h->match = IPmatchaddr;
623                         else
624                                 h->match = IPmatchpa;
625                 } else {
626                         if (c->lport == 0)
627                                 h->match = IPmatchany;
628                         else
629                                 h->match = IPmatchport;
630                 }
631         }
632         h->c = c;
633
634         spin_lock(&ht->lock);
635         h->next = ht->tab[hv];
636         ht->tab[hv] = h;
637         spin_unlock(&ht->lock);
638 }
639
640 void iphtrem(struct Ipht *ht, struct conv *c)
641 {
642         uint32_t hv;
643         struct Iphash **l, *h;
644
645         hv = iphash(c->raddr, c->rport, c->laddr, c->lport);
646         spin_lock(&ht->lock);
647         for (l = &ht->tab[hv]; (*l) != NULL; l = &(*l)->next)
648                 if ((*l)->c == c) {
649                         h = *l;
650                         (*l) = h->next;
651                         kfree(h);
652                         break;
653                 }
654         spin_unlock(&ht->lock);
655 }
656
657 /* look for a matching conversation with the following precedence
658  *      connected && raddr,rport,laddr,lport
659  *      announced && laddr,lport
660  *      announced && *,lport
661  *      announced && laddr,*
662  *      announced && *,*
663  */
664 struct conv *iphtlook(struct Ipht *ht, uint8_t * sa, uint16_t sp, uint8_t * da,
665                                           uint16_t dp)
666 {
667         uint32_t hv;
668         struct Iphash *h;
669         struct conv *c;
670
671         /* exact 4 pair match (connection) */
672         hv = iphash(sa, sp, da, dp);
673         spin_lock(&ht->lock);
674         for (h = ht->tab[hv]; h != NULL; h = h->next) {
675                 if (h->match != IPmatchexact)
676                         continue;
677                 c = h->c;
678                 if (sp == c->rport && dp == c->lport
679                         && ipcmp(sa, c->raddr) == 0 && ipcmp(da, c->laddr) == 0) {
680                         spin_unlock(&ht->lock);
681                         return c;
682                 }
683         }
684
685         /* match local address and port */
686         hv = iphash(IPnoaddr, 0, da, dp);
687         for (h = ht->tab[hv]; h != NULL; h = h->next) {
688                 if (h->match != IPmatchpa)
689                         continue;
690                 c = h->c;
691                 if (dp == c->lport && ipcmp(da, c->laddr) == 0) {
692                         spin_unlock(&ht->lock);
693                         return c;
694                 }
695         }
696
697         /* match just port */
698         hv = iphash(IPnoaddr, 0, IPnoaddr, dp);
699         for (h = ht->tab[hv]; h != NULL; h = h->next) {
700                 if (h->match != IPmatchport)
701                         continue;
702                 c = h->c;
703                 if (dp == c->lport) {
704                         spin_unlock(&ht->lock);
705                         return c;
706                 }
707         }
708
709         /* match local address */
710         hv = iphash(IPnoaddr, 0, da, 0);
711         for (h = ht->tab[hv]; h != NULL; h = h->next) {
712                 if (h->match != IPmatchaddr)
713                         continue;
714                 c = h->c;
715                 if (ipcmp(da, c->laddr) == 0) {
716                         spin_unlock(&ht->lock);
717                         return c;
718                 }
719         }
720
721         /* look for something that matches anything */
722         hv = iphash(IPnoaddr, 0, IPnoaddr, 0);
723         for (h = ht->tab[hv]; h != NULL; h = h->next) {
724                 if (h->match != IPmatchany)
725                         continue;
726                 c = h->c;
727                 spin_unlock(&ht->lock);
728                 return c;
729         }
730         spin_unlock(&ht->lock);
731         return NULL;
732 }