4c1072be5f29a09ec66675ba268875b155772839
[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 <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
43 /*
44  *  address resolution tables
45  */
46
47 enum {
48         NHASH = (1 << 6),
49         NCACHE = 256,
50
51         AOK = 1,
52         AWAIT = 2,
53 };
54
55 char *arpstate[] = {
56         "UNUSED",
57         "OK",
58         "WAIT",
59 };
60
61 /*
62  *  one per Fs
63  */
64 struct arp {
65         qlock_t qlock;
66         struct Fs *f;
67         struct arpent *hash[NHASH];
68         struct arpent cache[NCACHE];
69         struct arpent *rxmt;
70         struct proc *rxmitp;            /* neib sol re-transmit proc */
71         struct rendez rxmtq;
72         struct block *dropf, *dropl;
73 };
74
75 #define haship(s) ((s)[IPaddrlen-1]%NHASH)
76
77 int ReTransTimer = RETRANS_TIMER;
78 static void rxmitproc(void *v);
79
80 void arpinit(struct Fs *f)
81 {
82         f->arp = kzmalloc(sizeof(struct arp), KMALLOC_WAIT);
83         qlock_init(&f->arp->qlock);
84         rendez_init(&f->arp->rxmtq);
85         f->arp->f = f;
86         f->arp->rxmt = NULL;
87         f->arp->dropf = f->arp->dropl = NULL;
88         ktask("rxmitproc", rxmitproc, f->arp);
89 }
90
91 /*
92  *  create a new arp entry for an ip address.
93  */
94 static struct arpent *newarp6(struct arp *arp, uint8_t * ip, struct Ipifc *ifc,
95                                                           int addrxt)
96 {
97         unsigned int t;
98         struct block *next, *xp;
99         struct arpent *a, *e, *f, **l;
100         struct medium *m = ifc->m;
101         int empty;
102
103         /* find oldest entry */
104         e = &arp->cache[NCACHE];
105         a = arp->cache;
106         t = a->utime;
107         for (f = a; f < e; f++) {
108                 if (f->utime < t) {
109                         t = f->utime;
110                         a = f;
111                 }
112         }
113
114         /* dump waiting packets */
115         xp = a->hold;
116         a->hold = NULL;
117
118         if (isv4(a->ip)) {
119                 while (xp) {
120                         next = xp->list;
121                         freeblist(xp);
122                         xp = next;
123                 }
124         } else {        // queue icmp unreachable for rxmitproc later on, 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
333 arpenter(struct Fs *fs, int version, uint8_t * ip, uint8_t * mac, int n,
334                  int refresh)
335 {
336         ERRSTACK(1);
337         struct arp *arp;
338         struct route *r;
339         struct arpent *a, *f, **l;
340         struct Ipifc *ifc;
341         struct medium *type;
342         struct block *bp, *next;
343         uint8_t v6ip[IPaddrlen];
344
345         arp = fs->arp;
346
347         if (n != 6) {
348 //      print("arp: len = %d\n", n);
349                 return;
350         }
351
352         switch (version) {
353                 case V4:
354                         r = v4lookup(fs, ip, NULL);
355                         v4tov6(v6ip, ip);
356                         ip = v6ip;
357                         break;
358                 case V6:
359                         r = v6lookup(fs, ip, NULL);
360                         break;
361                 default:
362                         panic("arpenter: version %d", version);
363                         return; /* to supress warnings */
364         }
365
366         if (r == NULL) {
367 //      print("arp: no route for entry\n");
368                 return;
369         }
370
371         ifc = r->rt.ifc;
372         type = ifc->m;
373
374         qlock(&arp->qlock);
375         for (a = arp->hash[haship(ip)]; a; a = a->hash) {
376                 if (a->type != type || (a->state != AWAIT && a->state != AOK))
377                         continue;
378
379                 if (ipcmp(a->ip, ip) == 0) {
380                         a->state = AOK;
381                         memmove(a->mac, mac, type->maclen);
382
383                         if (version == V6) {
384                                 /* take out of re-transmit chain */
385                                 l = &arp->rxmt;
386                                 for (f = *l; f; f = f->nextrxt) {
387                                         if (f == a) {
388                                                 *l = a->nextrxt;
389                                                 break;
390                                         }
391                                         l = &f->nextrxt;
392                                 }
393                         }
394
395                         a->ifc = ifc;
396                         a->ifcid = ifc->ifcid;
397                         bp = a->hold;
398                         a->hold = NULL;
399                         if (version == V4)
400                                 ip += IPv4off;
401                         a->utime = NOW;
402                         a->ctime = a->utime;
403                         qunlock(&arp->qlock);
404
405                         while (bp) {
406                                 next = bp->list;
407                                 if (ifc != NULL) {
408                                         if (waserror()) {
409                                                 runlock(&ifc->rwlock);
410                                                 nexterror();
411                                         }
412                                         rlock(&ifc->rwlock);
413                                         if (ifc->m != NULL)
414                                                 ifc->m->bwrite(ifc, bp, version, ip);
415                                         else
416                                                 freeb(bp);
417                                         runlock(&ifc->rwlock);
418                                         poperror();
419                                 } else
420                                         freeb(bp);
421                                 bp = next;
422                         }
423                         return;
424                 }
425         }
426
427         if (refresh == 0) {
428                 a = newarp6(arp, ip, ifc, 0);
429                 a->state = AOK;
430                 a->type = type;
431                 a->ctime = NOW;
432                 memmove(a->mac, mac, type->maclen);
433         }
434
435         qunlock(&arp->qlock);
436 }
437
438 int arpwrite(struct Fs *fs, char *s, int len)
439 {
440         int n;
441         struct route *r;
442         struct arp *arp;
443         struct block *bp;
444         struct arpent *a, *fl, **l;
445         struct medium *m;
446         char *f[4], buf[256];
447         uint8_t ip[IPaddrlen], mac[MAClen];
448
449         arp = fs->arp;
450
451         if (len == 0)
452                 error(EINVAL, NULL);
453         if (len >= sizeof(buf))
454                 len = sizeof(buf) - 1;
455         strncpy(buf, s, len);
456         buf[len] = 0;
457         if (len > 0 && buf[len - 1] == '\n')
458                 buf[len - 1] = 0;
459
460         n = getfields(buf, f, 4, 1, " ");
461         if (strcmp(f[0], "flush") == 0) {
462                 qlock(&arp->qlock);
463                 for (a = arp->cache; a < &arp->cache[NCACHE]; a++) {
464                         memset(a->ip, 0, sizeof(a->ip));
465                         memset(a->mac, 0, sizeof(a->mac));
466                         a->hash = NULL;
467                         a->state = 0;
468                         a->utime = 0;
469                         while (a->hold != NULL) {
470                                 bp = a->hold->list;
471                                 freeblist(a->hold);
472                                 a->hold = bp;
473                         }
474                 }
475                 memset(arp->hash, 0, sizeof(arp->hash));
476 // clear all pkts on these lists (rxmt, dropf/l)
477                 arp->rxmt = NULL;
478                 arp->dropf = NULL;
479                 arp->dropl = NULL;
480                 qunlock(&arp->qlock);
481         } else if (strcmp(f[0], "add") == 0) {
482                 switch (n) {
483                         default:
484                                 error(EINVAL, NULL);
485                         case 3:
486                                 parseip(ip, f[1]);
487                                 if (isv4(ip))
488                                         r = v4lookup(fs, ip + IPv4off, NULL);
489                                 else
490                                         r = v6lookup(fs, ip, NULL);
491                                 if (r == NULL)
492                                         error(EHOSTUNREACH, "Destination unreachable");
493                                 m = r->rt.ifc->m;
494                                 n = parsemac(mac, f[2], m->maclen);
495                                 break;
496                         case 4:
497                                 m = ipfindmedium(f[1]);
498                                 if (m == NULL)
499                                         error(EINVAL, NULL);
500                                 parseip(ip, f[2]);
501                                 n = parsemac(mac, f[3], m->maclen);
502                                 break;
503                 }
504
505                 if (m->ares == NULL)
506                         error(EINVAL, NULL);
507
508                 m->ares(fs, V6, ip, mac, n, 0);
509         } else if (strcmp(f[0], "del") == 0) {
510                 if (n != 2)
511                         error(EINVAL, NULL);
512
513                 parseip(ip, f[1]);
514                 qlock(&arp->qlock);
515
516                 l = &arp->hash[haship(ip)];
517                 for (a = *l; a; a = a->hash) {
518                         if (memcmp(ip, a->ip, sizeof(a->ip)) == 0) {
519                                 *l = a->hash;
520                                 break;
521                         }
522                         l = &a->hash;
523                 }
524
525                 if (a) {
526                         /* take out of re-transmit chain */
527                         l = &arp->rxmt;
528                         for (fl = *l; fl; fl = fl->nextrxt) {
529                                 if (fl == a) {
530                                         *l = a->nextrxt;
531                                         break;
532                                 }
533                                 l = &fl->nextrxt;
534                         }
535
536                         a->nextrxt = NULL;
537                         a->hash = NULL;
538                         a->hold = NULL;
539                         a->last = NULL;
540                         a->ifc = NULL;
541                         memset(a->ip, 0, sizeof(a->ip));
542                         memset(a->mac, 0, sizeof(a->mac));
543                 }
544                 qunlock(&arp->qlock);
545         } else
546                 error(EINVAL, NULL);
547
548         return len;
549 }
550
551 enum {
552         Alinelen = 90,
553 };
554
555 static char *aformat = "%-6.6s %-8.8s %-40.40I %E\n";
556
557 int arpread(struct arp *arp, char *p, uint32_t offset, int len)
558 {
559         struct arpent *a;
560         int n;
561         int left = len;
562         int amt;
563
564         if (offset % Alinelen)
565                 return 0;
566
567         offset = offset / Alinelen;
568         len = len / Alinelen;
569
570         n = 0;
571         for (a = arp->cache; len > 0 && a < &arp->cache[NCACHE]; a++) {
572                 if (a->state == 0)
573                         continue;
574                 if (offset > 0) {
575                         offset--;
576                         continue;
577                 }
578                 len--;
579                 left--;
580                 qlock(&arp->qlock);
581                 amt = snprintf(p + n, left, aformat, a->type->name, arpstate[a->state],
582                                a->ip, a->mac);
583                 n += amt;
584                 left -= amt;
585                 qunlock(&arp->qlock);
586         }
587
588         return n;
589 }
590
591 static uint64_t rxmitsols(struct arp *arp)
592 {
593         unsigned int sflag;
594         struct block *next, *xp;
595         struct arpent *a, *b, **l;
596         struct Fs *f;
597         uint8_t ipsrc[IPaddrlen];
598         struct Ipifc *ifc = NULL;
599         uint64_t nrxt;
600
601         qlock(&arp->qlock);
602         f = arp->f;
603
604         a = arp->rxmt;
605         if (a == NULL) {
606                 nrxt = 0;
607                 goto dodrops;   //return nrxt;
608         }
609         nrxt = a->rtime - NOW;
610         if (nrxt > 3 * ReTransTimer / 4)
611                 goto dodrops;   //return nrxt;
612
613         for (; a; a = a->nextrxt) {
614                 ifc = a->ifc;
615                 assert(ifc != NULL);
616                 if ((a->rxtsrem <= 0) || !(canrlock(&ifc->rwlock))
617                         || (a->ifcid != ifc->ifcid)) {
618                         xp = a->hold;
619                         a->hold = NULL;
620
621                         if (xp) {
622                                 if (arp->dropl == NULL)
623                                         arp->dropf = xp;
624                                 else
625                                         arp->dropl->list = xp;
626                         }
627
628                         cleanarpent(arp, a);
629                 } else
630                         break;
631         }
632         if (a == NULL)
633                 goto dodrops;
634
635         qunlock(&arp->qlock);   /* for icmpns */
636         if ((sflag = ipv6anylocal(ifc, ipsrc)) != SRC_UNSPEC)
637                 icmpns(f, ipsrc, sflag, a->ip, TARG_MULTI, ifc->mac);
638
639         runlock(&ifc->rwlock);
640         qlock(&arp->qlock);
641
642         /* put to the end of re-transmit chain */
643         l = &arp->rxmt;
644         for (b = *l; b; b = b->nextrxt) {
645                 if (b == a) {
646                         *l = a->nextrxt;
647                         break;
648                 }
649                 l = &b->nextrxt;
650         }
651         for (b = *l; b; b = b->nextrxt) {
652                 l = &b->nextrxt;
653         }
654         *l = a;
655         a->rxtsrem--;
656         a->nextrxt = NULL;
657         a->rtime = NOW + ReTransTimer;
658
659         a = arp->rxmt;
660         if (a == NULL)
661                 nrxt = 0;
662         else
663                 nrxt = a->rtime - NOW;
664
665 dodrops:
666         xp = arp->dropf;
667         arp->dropf = NULL;
668         arp->dropl = NULL;
669         qunlock(&arp->qlock);
670
671         for (; xp; xp = next) {
672                 next = xp->list;
673                 icmphostunr(f, ifc, xp, icmp6_adr_unreach, 1);
674         }
675
676         return nrxt;
677
678 }
679
680 static int rxready(void *v)
681 {
682         struct arp *arp = (struct arp *)v;
683         int x;
684
685         x = ((arp->rxmt != NULL) || (arp->dropf != NULL));
686
687         return x;
688 }
689
690 static void rxmitproc(void *v)
691 {
692         ERRSTACK(2);
693         struct arp *arp = v;
694         uint64_t wakeupat;
695
696         arp->rxmitp = current;
697         //print("arp rxmitproc started\n");
698         if (waserror()) {
699                 arp->rxmitp = 0;
700                 poperror();
701                 warn("arp rxmit ktask exited");
702                 return;
703         }
704         for (;;) {
705                 wakeupat = rxmitsols(arp);
706                 if (wakeupat == 0)
707                         rendez_sleep(&arp->rxmtq, rxready, v);
708                 else if (wakeupat > ReTransTimer / 4)
709                         kthread_usleep(wakeupat * 1000);
710         }
711         poperror();
712 }