Replace '//' comments with '/* */' to be
[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), MEM_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 {
125                 /* queue icmp unreachable for rxmitproc later, w/o arp lock */
126                 if (xp) {
127                         if (arp->dropl == NULL)
128                                 arp->dropf = xp;
129                         else
130                                 arp->dropl->list = xp;
131
132                         for (next = xp->list; next; next = next->list)
133                                 xp = next;
134                         arp->dropl = xp;
135                         rendez_wakeup(&arp->rxmtq);
136                 }
137         }
138
139         /* take out of current chain */
140         l = &arp->hash[haship(a->ip)];
141         for (f = *l; f; f = f->hash) {
142                 if (f == a) {
143                         *l = a->hash;
144                         break;
145                 }
146                 l = &f->hash;
147         }
148
149         /* insert into new chain */
150         l = &arp->hash[haship(ip)];
151         a->hash = *l;
152         *l = a;
153
154         memmove(a->ip, ip, sizeof(a->ip));
155         a->utime = NOW;
156         a->ctime = 0;   /* somewhat of a "last sent time".  0, to trigger a send. */
157         a->type = m;
158
159         a->rtime = NOW + ReTransTimer;
160         a->rxtsrem = MAX_MULTICAST_SOLICIT;
161         a->ifc = ifc;
162         a->ifcid = ifc->ifcid;
163
164         /* put to the end of re-transmit chain; addrxt is 0 when isv4(a->ip) */
165         if (!ipismulticast(a->ip) && addrxt) {
166                 l = &arp->rxmt;
167                 empty = (*l == NULL);
168
169                 for (f = *l; f; f = f->nextrxt) {
170                         if (f == a) {
171                                 *l = a->nextrxt;
172                                 break;
173                         }
174                         l = &f->nextrxt;
175                 }
176                 for (f = *l; f; f = f->nextrxt) {
177                         l = &f->nextrxt;
178                 }
179                 *l = a;
180                 if (empty)
181                         rendez_wakeup(&arp->rxmtq);
182         }
183
184         a->nextrxt = NULL;
185
186         return a;
187 }
188
189 /* called with arp qlocked */
190
191 void cleanarpent(struct arp *arp, struct arpent *a)
192 {
193         struct arpent *f, **l;
194
195         a->utime = 0;
196         a->ctime = 0;
197         a->type = 0;
198         a->state = 0;
199
200         /* take out of current chain */
201         l = &arp->hash[haship(a->ip)];
202         for (f = *l; f; f = f->hash) {
203                 if (f == a) {
204                         *l = a->hash;
205                         break;
206                 }
207                 l = &f->hash;
208         }
209
210         /* take out of re-transmit chain */
211         l = &arp->rxmt;
212         for (f = *l; f; f = f->nextrxt) {
213                 if (f == a) {
214                         *l = a->nextrxt;
215                         break;
216                 }
217                 l = &f->nextrxt;
218         }
219         a->nextrxt = NULL;
220         a->hash = NULL;
221         a->hold = NULL;
222         a->last = NULL;
223         a->ifc = NULL;
224 }
225
226 /*
227  *  fill in the media address if we have it.  Otherwise return an
228  *  arpent that represents the state of the address resolution FSM
229  *  for ip.  Add the packet to be sent onto the list of packets
230  *  waiting for ip->mac to be resolved.
231  */
232 struct arpent *arpget(struct arp *arp, struct block *bp, int version,
233                                           struct Ipifc *ifc, uint8_t * ip, uint8_t * mac)
234 {
235         int hash, len;
236         struct arpent *a;
237         struct medium *type = ifc->m;
238         uint8_t v6ip[IPaddrlen];
239         uint16_t *s, *d;
240
241         if (version == V4) {
242                 v4tov6(v6ip, ip);
243                 ip = v6ip;
244         }
245
246         qlock(&arp->qlock);
247         hash = haship(ip);
248         for (a = arp->hash[hash]; a; a = a->hash) {
249                 if (ipcmp(ip, a->ip) == 0)
250                         if (type == a->type)
251                                 break;
252         }
253
254         if (a == NULL) {
255                 a = newarp6(arp, ip, ifc, (version != V4));
256                 a->state = AWAIT;
257         }
258         a->utime = NOW;
259         if (a->state == AWAIT) {
260                 if (bp != NULL) {
261                         if (a->hold)
262                                 a->last->list = bp;
263                         else
264                                 a->hold = bp;
265                         a->last = bp;
266                         bp->list = NULL;
267                 }
268                 return a;       /* return with arp qlocked */
269         }
270
271         s = (uint16_t *)a->mac;
272         d = (uint16_t *)mac;
273         len = a->type->maclen / 2;
274         while (len) {
275                 *d++ = *s++;
276                 len--;
277         }
278
279         /* remove old entries */
280         if (NOW - a->ctime > 15 * 60 * 1000)
281                 cleanarpent(arp, a);
282
283         qunlock(&arp->qlock);
284         return NULL;
285 }
286
287 /*
288  * called with arp locked
289  */
290 void arprelease(struct arp *arp, struct arpent *a)
291 {
292         qunlock(&arp->qlock);
293 }
294
295 /*
296  * Copy out the mac address from the arpent.  Return the
297  * block waiting to get sent to this mac address.
298  *
299  * called with arp locked
300  */
301 struct block *arpresolve(struct arp *arp, struct arpent *a, struct medium *type,
302                                                  uint8_t * mac)
303 {
304         struct block *bp;
305         struct arpent *f, **l;
306
307         if (!isv4(a->ip)) {
308                 l = &arp->rxmt;
309                 for (f = *l; f; f = f->nextrxt) {
310                         if (f == a) {
311                                 *l = a->nextrxt;
312                                 break;
313                         }
314                         l = &f->nextrxt;
315                 }
316         }
317
318         memmove(a->mac, mac, type->maclen);
319         a->type = type;
320         a->state = AOK;
321         a->utime = NOW;
322         bp = a->hold;
323         a->hold = NULL;
324         /* brho: it looks like we return the entire hold list, though it might be
325          * purged by now via some other crazy arp list management.  our callers
326          * can't handle the arp's b->list stuff. */
327         assert(!bp->list);
328         qunlock(&arp->qlock);
329
330         return bp;
331 }
332
333 void
334 arpenter(struct Fs *fs, int version, uint8_t * ip, uint8_t * mac, int n,
335                  int refresh)
336 {
337         ERRSTACK(1);
338         struct arp *arp;
339         struct route *r;
340         struct arpent *a, *f, **l;
341         struct Ipifc *ifc;
342         struct medium *type;
343         struct block *bp, *next;
344         uint8_t v6ip[IPaddrlen];
345
346         arp = fs->arp;
347
348         if (n != 6) {
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                 return;
368         }
369
370         ifc = r->rt.ifc;
371         type = ifc->m;
372
373         qlock(&arp->qlock);
374         for (a = arp->hash[haship(ip)]; a; a = a->hash) {
375                 if (a->type != type || (a->state != AWAIT && a->state != AOK))
376                         continue;
377
378                 if (ipcmp(a->ip, ip) == 0) {
379                         a->state = AOK;
380                         memmove(a->mac, mac, type->maclen);
381
382                         if (version == V6) {
383                                 /* take out of re-transmit chain */
384                                 l = &arp->rxmt;
385                                 for (f = *l; f; f = f->nextrxt) {
386                                         if (f == a) {
387                                                 *l = a->nextrxt;
388                                                 break;
389                                         }
390                                         l = &f->nextrxt;
391                                 }
392                         }
393
394                         a->ifc = ifc;
395                         a->ifcid = ifc->ifcid;
396                         bp = a->hold;
397                         a->hold = NULL;
398                         if (version == V4)
399                                 ip += IPv4off;
400                         a->utime = NOW;
401                         a->ctime = a->utime;
402                         qunlock(&arp->qlock);
403
404                         while (bp) {
405                                 next = bp->list;
406                                 if (ifc != NULL) {
407                                         rlock(&ifc->rwlock);
408                                         if (waserror()) {
409                                                 runlock(&ifc->rwlock);
410                                                 nexterror();
411                                         }
412                                         if (ifc->m != NULL)
413                                                 ifc->m->bwrite(ifc, bp, version, ip);
414                                         else
415                                                 freeb(bp);
416                                         runlock(&ifc->rwlock);
417                                         poperror();
418                                 } else
419                                         freeb(bp);
420                                 bp = next;
421                         }
422                         return;
423                 }
424         }
425
426         if (refresh == 0) {
427                 a = newarp6(arp, ip, ifc, 0);
428                 a->state = AOK;
429                 a->type = type;
430                 a->ctime = NOW;
431                 memmove(a->mac, mac, type->maclen);
432         }
433
434         qunlock(&arp->qlock);
435 }
436
437 int arpwrite(struct Fs *fs, char *s, long len)
438 {
439         int n;
440         struct route *r;
441         struct arp *arp;
442         struct block *bp;
443         struct arpent *a, *fl, **l;
444         struct medium *m;
445         char *f[4], buf[256];
446         uint8_t ip[IPaddrlen], mac[MAClen];
447
448         arp = fs->arp;
449
450         if (len <= 0)
451                 error(EINVAL, ERROR_FIXME);
452         if (len > sizeof(buf))
453                 len = sizeof(buf);
454         strlcpy(buf, s, sizeof(buf));
455         if (len > 0 && buf[len - 2] == '\n')
456                 buf[len - 2] = 0;
457
458         n = getfields(buf, f, 4, 1, " ");
459         if (strcmp(f[0], "flush") == 0) {
460                 qlock(&arp->qlock);
461                 for (a = arp->cache; a < &arp->cache[NCACHE]; a++) {
462                         memset(a->ip, 0, sizeof(a->ip));
463                         memset(a->mac, 0, sizeof(a->mac));
464                         a->hash = NULL;
465                         a->state = 0;
466                         a->utime = 0;
467                         while (a->hold != NULL) {
468                                 bp = a->hold->list;
469                                 freeblist(a->hold);
470                                 a->hold = bp;
471                         }
472                 }
473                 memset(arp->hash, 0, sizeof(arp->hash));
474                 /* clear all pkts on these lists (rxmt, dropf/l) */
475                 arp->rxmt = NULL;
476                 arp->dropf = NULL;
477                 arp->dropl = NULL;
478                 qunlock(&arp->qlock);
479         } else if (strcmp(f[0], "add") == 0) {
480                 switch (n) {
481                         default:
482                                 error(EINVAL, ERROR_FIXME);
483                         case 3:
484                                 parseip(ip, f[1]);
485                                 if (isv4(ip))
486                                         r = v4lookup(fs, ip + IPv4off, NULL);
487                                 else
488                                         r = v6lookup(fs, ip, NULL);
489                                 if (r == NULL)
490                                         error(EHOSTUNREACH, "Destination unreachable");
491                                 m = r->rt.ifc->m;
492                                 n = parsemac(mac, f[2], m->maclen);
493                                 break;
494                         case 4:
495                                 m = ipfindmedium(f[1]);
496                                 if (m == NULL)
497                                         error(EINVAL, ERROR_FIXME);
498                                 parseip(ip, f[2]);
499                                 n = parsemac(mac, f[3], m->maclen);
500                                 break;
501                 }
502
503                 if (m->ares == NULL)
504                         error(EINVAL, ERROR_FIXME);
505
506                 m->ares(fs, V6, ip, mac, n, 0);
507         } else if (strcmp(f[0], "del") == 0) {
508                 if (n != 2)
509                         error(EINVAL, ERROR_FIXME);
510
511                 parseip(ip, f[1]);
512                 qlock(&arp->qlock);
513
514                 l = &arp->hash[haship(ip)];
515                 for (a = *l; a; a = a->hash) {
516                         if (memcmp(ip, a->ip, sizeof(a->ip)) == 0) {
517                                 *l = a->hash;
518                                 break;
519                         }
520                         l = &a->hash;
521                 }
522
523                 if (a) {
524                         /* take out of re-transmit chain */
525                         l = &arp->rxmt;
526                         for (fl = *l; fl; fl = fl->nextrxt) {
527                                 if (fl == a) {
528                                         *l = a->nextrxt;
529                                         break;
530                                 }
531                                 l = &fl->nextrxt;
532                         }
533
534                         a->nextrxt = NULL;
535                         a->hash = NULL;
536                         a->hold = NULL;
537                         a->last = NULL;
538                         a->ifc = NULL;
539                         memset(a->ip, 0, sizeof(a->ip));
540                         memset(a->mac, 0, sizeof(a->mac));
541                 }
542                 qunlock(&arp->qlock);
543         } else
544                 error(EINVAL, ERROR_FIXME);
545
546         return len;
547 }
548
549 enum {
550         Alinelen = 90,
551 };
552
553 static char *aformat = "%-6.6s %-8.8s %-40.40I %E\n";
554
555 int arpread(struct arp *arp, char *p, uint32_t offset, int len)
556 {
557         struct arpent *a;
558         int n;
559         int left = len;
560         int amt;
561
562         if (offset % Alinelen)
563                 return 0;
564
565         offset = offset / Alinelen;
566         len = len / Alinelen;
567
568         n = 0;
569         for (a = arp->cache; len > 0 && a < &arp->cache[NCACHE]; a++) {
570                 if (a->state == 0)
571                         continue;
572                 if (offset > 0) {
573                         offset--;
574                         continue;
575                 }
576                 len--;
577                 left--;
578                 qlock(&arp->qlock);
579                 amt = snprintf(p + n, left, aformat, a->type->name, 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 }