vfs: Remove KFS, blockdev and devfs
[akaros.git] / kern / src / net / arp.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 <slab.h>
31 #include <kmalloc.h>
32 #include <kref.h>
33 #include <string.h>
34 #include <stdio.h>
35 #include <assert.h>
36 #include <error.h>
37 #include <cpio.h>
38 #include <pmap.h>
39 #include <smp.h>
40 #include <net/ip.h>
41
42 /*
43  *  address resolution tables
44  */
45
46 enum {
47         NHASH = (1 << 6),
48         NCACHE = 256,
49
50         AOK = 1,
51         AWAIT = 2,
52 };
53
54 char *arpstate[] = {
55         "UNUSED",
56         "OK",
57         "WAIT",
58 };
59
60 /*
61  *  one per Fs
62  */
63 struct arp {
64         qlock_t qlock;
65         struct Fs *f;
66         struct arpent *hash[NHASH];
67         struct arpent cache[NCACHE];
68         struct arpent *rxmt;
69         struct proc *rxmitp;            /* neib sol re-transmit proc */
70         struct rendez rxmtq;
71         struct block *dropf, *dropl;
72 };
73
74 #define haship(s) ((s)[IPaddrlen-1]%NHASH)
75
76 int ReTransTimer = RETRANS_TIMER;
77 static void rxmitproc(void *v);
78
79 void arpinit(struct Fs *f)
80 {
81         f->arp = kzmalloc(sizeof(struct arp), MEM_WAIT);
82         qlock_init(&f->arp->qlock);
83         rendez_init(&f->arp->rxmtq);
84         f->arp->f = f;
85         f->arp->rxmt = NULL;
86         f->arp->dropf = f->arp->dropl = NULL;
87         ktask("rxmitproc", rxmitproc, f->arp);
88 }
89
90 /*
91  *  create a new arp entry for an ip address.
92  */
93 static struct arpent *newarp6(struct arp *arp, uint8_t *ip, struct Ipifc *ifc,
94                               int addrxt)
95 {
96         unsigned int t;
97         struct block *next, *xp;
98         struct arpent *a, *e, *f, **l;
99         struct medium *m = ifc->m;
100         int empty;
101
102         /* find oldest entry */
103         e = &arp->cache[NCACHE];
104         a = arp->cache;
105         t = a->utime;
106         for (f = a; f < e; f++) {
107                 if (f->utime < t) {
108                         t = f->utime;
109                         a = f;
110                 }
111         }
112
113         /* dump waiting packets */
114         xp = a->hold;
115         a->hold = NULL;
116
117         if (isv4(a->ip)) {
118                 while (xp) {
119                         next = xp->list;
120                         freeblist(xp);
121                         xp = next;
122                 }
123         } else {
124                 /* queue icmp unreachable for rxmitproc later, w/o arp lock */
125                 if (xp) {
126                         if (arp->dropl == NULL)
127                                 arp->dropf = xp;
128                         else
129                                 arp->dropl->list = xp;
130
131                         for (next = xp->list; next; next = next->list)
132                                 xp = next;
133                         arp->dropl = xp;
134                         rendez_wakeup(&arp->rxmtq);
135                 }
136         }
137
138         /* take out of current chain */
139         l = &arp->hash[haship(a->ip)];
140         for (f = *l; f; f = f->hash) {
141                 if (f == a) {
142                         *l = a->hash;
143                         break;
144                 }
145                 l = &f->hash;
146         }
147
148         /* insert into new chain */
149         l = &arp->hash[haship(ip)];
150         a->hash = *l;
151         *l = a;
152
153         memmove(a->ip, ip, sizeof(a->ip));
154         a->utime = NOW;
155         a->ctime = 0;   /* somewhat of a "last sent time".  0, to trigger a send. */
156         a->type = m;
157
158         a->rtime = NOW + ReTransTimer;
159         a->rxtsrem = MAX_MULTICAST_SOLICIT;
160         a->ifc = ifc;
161         a->ifcid = ifc->ifcid;
162
163         /* put to the end of re-transmit chain; addrxt is 0 when isv4(a->ip) */
164         if (!ipismulticast(a->ip) && addrxt) {
165                 l = &arp->rxmt;
166                 empty = (*l == NULL);
167
168                 for (f = *l; f; f = f->nextrxt) {
169                         if (f == a) {
170                                 *l = a->nextrxt;
171                                 break;
172                         }
173                         l = &f->nextrxt;
174                 }
175                 for (f = *l; f; f = f->nextrxt) {
176                         l = &f->nextrxt;
177                 }
178                 *l = a;
179                 if (empty)
180                         rendez_wakeup(&arp->rxmtq);
181         }
182
183         a->nextrxt = NULL;
184
185         return a;
186 }
187
188 /* called with arp qlocked */
189
190 void cleanarpent(struct arp *arp, struct arpent *a)
191 {
192         struct arpent *f, **l;
193
194         a->utime = 0;
195         a->ctime = 0;
196         a->type = 0;
197         a->state = 0;
198
199         /* take out of current chain */
200         l = &arp->hash[haship(a->ip)];
201         for (f = *l; f; f = f->hash) {
202                 if (f == a) {
203                         *l = a->hash;
204                         break;
205                 }
206                 l = &f->hash;
207         }
208
209         /* take out of re-transmit chain */
210         l = &arp->rxmt;
211         for (f = *l; f; f = f->nextrxt) {
212                 if (f == a) {
213                         *l = a->nextrxt;
214                         break;
215                 }
216                 l = &f->nextrxt;
217         }
218         a->nextrxt = NULL;
219         a->hash = NULL;
220         a->hold = NULL;
221         a->last = NULL;
222         a->ifc = NULL;
223 }
224
225 /*
226  *  fill in the media address if we have it.  Otherwise return an
227  *  arpent that represents the state of the address resolution FSM
228  *  for ip.  Add the packet to be sent onto the list of packets
229  *  waiting for ip->mac to be resolved.
230  */
231 struct arpent *arpget(struct arp *arp, struct block *bp, int version,
232                       struct Ipifc *ifc, uint8_t *ip, uint8_t *mac)
233 {
234         int hash, len;
235         struct arpent *a;
236         struct medium *type = ifc->m;
237         uint8_t v6ip[IPaddrlen];
238         uint16_t *s, *d;
239
240         if (version == V4) {
241                 v4tov6(v6ip, ip);
242                 ip = v6ip;
243         }
244
245         qlock(&arp->qlock);
246         hash = haship(ip);
247         for (a = arp->hash[hash]; a; a = a->hash) {
248                 if (ipcmp(ip, a->ip) == 0)
249                         if (type == a->type)
250                                 break;
251         }
252
253         if (a == NULL) {
254                 a = newarp6(arp, ip, ifc, (version != V4));
255                 a->state = AWAIT;
256         }
257         a->utime = NOW;
258         if (a->state == AWAIT) {
259                 if (bp != NULL) {
260                         if (a->hold)
261                                 a->last->list = bp;
262                         else
263                                 a->hold = bp;
264                         a->last = bp;
265                         bp->list = NULL;
266                 }
267                 return a;       /* return with arp qlocked */
268         }
269
270         s = (uint16_t *)a->mac;
271         d = (uint16_t *)mac;
272         len = a->type->maclen / 2;
273         while (len) {
274                 *d++ = *s++;
275                 len--;
276         }
277
278         /* remove old entries */
279         if (NOW - a->ctime > 15 * 60 * 1000)
280                 cleanarpent(arp, a);
281
282         qunlock(&arp->qlock);
283         return NULL;
284 }
285
286 /*
287  * called with arp locked
288  */
289 void arprelease(struct arp *arp, struct arpent *a)
290 {
291         qunlock(&arp->qlock);
292 }
293
294 /*
295  * Copy out the mac address from the arpent.  Return the
296  * block waiting to get sent to this mac address.
297  *
298  * called with arp locked
299  */
300 struct block *arpresolve(struct arp *arp, struct arpent *a, struct medium *type,
301                          uint8_t *mac)
302 {
303         struct block *bp;
304         struct arpent *f, **l;
305
306         if (!isv4(a->ip)) {
307                 l = &arp->rxmt;
308                 for (f = *l; f; f = f->nextrxt) {
309                         if (f == a) {
310                                 *l = a->nextrxt;
311                                 break;
312                         }
313                         l = &f->nextrxt;
314                 }
315         }
316
317         memmove(a->mac, mac, type->maclen);
318         a->type = type;
319         a->state = AOK;
320         a->utime = NOW;
321         bp = a->hold;
322         a->hold = NULL;
323         /* brho: it looks like we return the entire hold list, though it might be
324          * purged by now via some other crazy arp list management.  our callers
325          * can't handle the arp's b->list stuff. */
326         assert(!bp->list);
327         qunlock(&arp->qlock);
328
329         return bp;
330 }
331
332 void arpenter(struct Fs *fs, int version, uint8_t *ip, uint8_t *mac, int n,
333               int refresh)
334 {
335         ERRSTACK(1);
336         struct arp *arp;
337         struct route *r;
338         struct arpent *a, *f, **l;
339         struct Ipifc *ifc;
340         struct medium *type;
341         struct block *bp, *next;
342         uint8_t v6ip[IPaddrlen];
343
344         arp = fs->arp;
345
346         if (n != 6) {
347                 return;
348         }
349
350         switch (version) {
351                 case V4:
352                         r = v4lookup(fs, ip, NULL);
353                         v4tov6(v6ip, ip);
354                         ip = v6ip;
355                         break;
356                 case V6:
357                         r = v6lookup(fs, ip, NULL);
358                         break;
359                 default:
360                         panic("arpenter: version %d", version);
361                         return; /* to supress warnings */
362         }
363
364         if (r == NULL) {
365                 return;
366         }
367
368         ifc = r->rt.ifc;
369         type = ifc->m;
370
371         qlock(&arp->qlock);
372         for (a = arp->hash[haship(ip)]; a; a = a->hash) {
373                 if (a->type != type || (a->state != AWAIT && a->state != AOK))
374                         continue;
375
376                 if (ipcmp(a->ip, ip) == 0) {
377                         a->state = AOK;
378                         memmove(a->mac, mac, type->maclen);
379
380                         if (version == V6) {
381                                 /* take out of re-transmit chain */
382                                 l = &arp->rxmt;
383                                 for (f = *l; f; f = f->nextrxt) {
384                                         if (f == a) {
385                                                 *l = a->nextrxt;
386                                                 break;
387                                         }
388                                         l = &f->nextrxt;
389                                 }
390                         }
391
392                         a->ifc = ifc;
393                         a->ifcid = ifc->ifcid;
394                         bp = a->hold;
395                         a->hold = NULL;
396                         if (version == V4)
397                                 ip += IPv4off;
398                         a->utime = NOW;
399                         a->ctime = a->utime;
400                         qunlock(&arp->qlock);
401
402                         while (bp) {
403                                 next = bp->list;
404                                 if (ifc != NULL) {
405                                         rlock(&ifc->rwlock);
406                                         if (waserror()) {
407                                                 runlock(&ifc->rwlock);
408                                                 nexterror();
409                                         }
410                                         if (ifc->m != NULL)
411                                                 ifc->m->bwrite(ifc, bp, version, ip);
412                                         else
413                                                 freeb(bp);
414                                         runlock(&ifc->rwlock);
415                                         poperror();
416                                 } else
417                                         freeb(bp);
418                                 bp = next;
419                         }
420                         return;
421                 }
422         }
423
424         if (refresh == 0) {
425                 a = newarp6(arp, ip, ifc, 0);
426                 a->state = AOK;
427                 a->type = type;
428                 a->ctime = NOW;
429                 memmove(a->mac, mac, type->maclen);
430         }
431
432         qunlock(&arp->qlock);
433 }
434
435 int arpwrite(struct Fs *fs, char *s, long len)
436 {
437         int n;
438         struct route *r;
439         struct arp *arp;
440         struct block *bp;
441         struct arpent *a, *fl, **l;
442         struct medium *m;
443         char *f[4], buf[256];
444         uint8_t ip[IPaddrlen], mac[MAClen];
445
446         arp = fs->arp;
447
448         if (len <= 0)
449                 error(EINVAL, ERROR_FIXME);
450         if (len > sizeof(buf))
451                 len = sizeof(buf);
452         strlcpy(buf, s, sizeof(buf));
453         if (len > 0 && buf[len - 2] == '\n')
454                 buf[len - 2] = 0;
455
456         n = getfields(buf, f, 4, 1, " ");
457         if (strcmp(f[0], "flush") == 0) {
458                 qlock(&arp->qlock);
459                 for (a = arp->cache; a < &arp->cache[NCACHE]; a++) {
460                         memset(a->ip, 0, sizeof(a->ip));
461                         memset(a->mac, 0, sizeof(a->mac));
462                         a->hash = NULL;
463                         a->state = 0;
464                         a->utime = 0;
465                         while (a->hold != NULL) {
466                                 bp = a->hold->list;
467                                 freeblist(a->hold);
468                                 a->hold = bp;
469                         }
470                 }
471                 memset(arp->hash, 0, sizeof(arp->hash));
472                 /* clear all pkts on these lists (rxmt, dropf/l) */
473                 arp->rxmt = NULL;
474                 arp->dropf = NULL;
475                 arp->dropl = NULL;
476                 qunlock(&arp->qlock);
477         } else if (strcmp(f[0], "add") == 0) {
478                 switch (n) {
479                         default:
480                                 error(EINVAL, ERROR_FIXME);
481                         case 3:
482                                 parseip(ip, f[1]);
483                                 if (isv4(ip))
484                                         r = v4lookup(fs, ip + IPv4off, NULL);
485                                 else
486                                         r = v6lookup(fs, ip, NULL);
487                                 if (r == NULL)
488                                         error(EHOSTUNREACH, "Destination unreachable");
489                                 m = r->rt.ifc->m;
490                                 n = parsemac(mac, f[2], m->maclen);
491                                 break;
492                         case 4:
493                                 m = ipfindmedium(f[1]);
494                                 if (m == NULL)
495                                         error(EINVAL, ERROR_FIXME);
496                                 parseip(ip, f[2]);
497                                 n = parsemac(mac, f[3], m->maclen);
498                                 break;
499                 }
500
501                 if (m->ares == NULL)
502                         error(EINVAL, ERROR_FIXME);
503
504                 m->ares(fs, V6, ip, mac, n, 0);
505         } else if (strcmp(f[0], "del") == 0) {
506                 if (n != 2)
507                         error(EINVAL, ERROR_FIXME);
508
509                 parseip(ip, f[1]);
510                 qlock(&arp->qlock);
511
512                 l = &arp->hash[haship(ip)];
513                 for (a = *l; a; a = a->hash) {
514                         if (memcmp(ip, a->ip, sizeof(a->ip)) == 0) {
515                                 *l = a->hash;
516                                 break;
517                         }
518                         l = &a->hash;
519                 }
520
521                 if (a) {
522                         /* take out of re-transmit chain */
523                         l = &arp->rxmt;
524                         for (fl = *l; fl; fl = fl->nextrxt) {
525                                 if (fl == a) {
526                                         *l = a->nextrxt;
527                                         break;
528                                 }
529                                 l = &fl->nextrxt;
530                         }
531
532                         a->nextrxt = NULL;
533                         a->hash = NULL;
534                         a->hold = NULL;
535                         a->last = NULL;
536                         a->ifc = NULL;
537                         memset(a->ip, 0, sizeof(a->ip));
538                         memset(a->mac, 0, sizeof(a->mac));
539                 }
540                 qunlock(&arp->qlock);
541         } else
542                 error(EINVAL, ERROR_FIXME);
543
544         return len;
545 }
546
547 enum {
548         Alinelen = 90,
549 };
550
551 static char *aformat = "%-6.6s %-8.8s %-40.40I %E\n";
552
553 int arpread(struct arp *arp, char *p, uint32_t offset, int len)
554 {
555         struct arpent *a;
556         int n;
557         int left = len;
558         int amt;
559
560         if (offset % Alinelen)
561                 return 0;
562
563         offset = offset / Alinelen;
564         len = len / Alinelen;
565
566         n = 0;
567         for (a = arp->cache; len > 0 && a < &arp->cache[NCACHE]; a++) {
568                 if (a->state == 0)
569                         continue;
570                 if (offset > 0) {
571                         offset--;
572                         continue;
573                 }
574                 len--;
575                 left--;
576                 qlock(&arp->qlock);
577                 amt = snprintf(p + n, left, aformat, a->type->name, arpstate[a->state],
578                                a->ip, a->mac);
579                 n += amt;
580                 left -= amt;
581                 qunlock(&arp->qlock);
582         }
583
584         return n;
585 }
586
587 static uint64_t rxmitsols(struct arp *arp)
588 {
589         unsigned int sflag;
590         struct block *next, *xp;
591         struct arpent *a, *b, **l;
592         struct Fs *f;
593         uint8_t ipsrc[IPaddrlen];
594         struct Ipifc *ifc = NULL;
595         uint64_t nrxt;
596
597         qlock(&arp->qlock);
598         f = arp->f;
599
600         a = arp->rxmt;
601         if (a == NULL) {
602                 nrxt = 0;
603                 goto dodrops;   /* return nrxt; */
604         }
605         nrxt = a->rtime - NOW;
606         if (nrxt > 3 * ReTransTimer / 4)
607                 goto dodrops;   /* return nrxt; */
608
609         for (; a; a = a->nextrxt) {
610                 ifc = a->ifc;
611                 assert(ifc != NULL);
612                 if ((a->rxtsrem <= 0) || !(canrlock(&ifc->rwlock))
613                         || (a->ifcid != ifc->ifcid)) {
614                         xp = a->hold;
615                         a->hold = NULL;
616
617                         if (xp) {
618                                 if (arp->dropl == NULL)
619                                         arp->dropf = xp;
620                                 else
621                                         arp->dropl->list = xp;
622                         }
623
624                         cleanarpent(arp, a);
625                 } else
626                         break;
627         }
628         if (a == NULL)
629                 goto dodrops;
630
631         qunlock(&arp->qlock);   /* for icmpns */
632         if ((sflag = ipv6anylocal(ifc, ipsrc)) != SRC_UNSPEC)
633                 icmpns(f, ipsrc, sflag, a->ip, TARG_MULTI, ifc->mac);
634
635         runlock(&ifc->rwlock);
636         qlock(&arp->qlock);
637
638         /* put to the end of re-transmit chain */
639         l = &arp->rxmt;
640         for (b = *l; b; b = b->nextrxt) {
641                 if (b == a) {
642                         *l = a->nextrxt;
643                         break;
644                 }
645                 l = &b->nextrxt;
646         }
647         for (b = *l; b; b = b->nextrxt) {
648                 l = &b->nextrxt;
649         }
650         *l = a;
651         a->rxtsrem--;
652         a->nextrxt = NULL;
653         a->rtime = NOW + ReTransTimer;
654
655         a = arp->rxmt;
656         if (a == NULL)
657                 nrxt = 0;
658         else
659                 nrxt = a->rtime - NOW;
660
661 dodrops:
662         xp = arp->dropf;
663         arp->dropf = NULL;
664         arp->dropl = NULL;
665         qunlock(&arp->qlock);
666
667         for (; xp; xp = next) {
668                 next = xp->list;
669                 icmphostunr(f, ifc, xp, icmp6_adr_unreach, 1);
670         }
671
672         return nrxt;
673
674 }
675
676 static int rxready(void *v)
677 {
678         struct arp *arp = (struct arp *)v;
679         int x;
680
681         x = ((arp->rxmt != NULL) || (arp->dropf != NULL));
682
683         return x;
684 }
685
686 static void rxmitproc(void *v)
687 {
688         ERRSTACK(2);
689         struct arp *arp = v;
690         uint64_t wakeupat;
691
692         arp->rxmitp = current;
693         if (waserror()) {
694                 arp->rxmitp = 0;
695                 poperror();
696                 warn("arp rxmit ktask exited");
697                 return;
698         }
699         for (;;) {
700                 wakeupat = rxmitsols(arp);
701                 if (wakeupat == 0)
702                         rendez_sleep(&arp->rxmtq, rxready, v);
703                 else if (wakeupat > ReTransTimer / 4)
704                         kthread_usleep(wakeupat * 1000);
705         }
706         poperror();
707 }