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