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