Minor whitespace cleanups in arp.c.
[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 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                 return;
349         }
350
351         switch (version) {
352                 case V4:
353                         r = v4lookup(fs, ip, NULL);
354                         v4tov6(v6ip, ip);
355                         ip = v6ip;
356                         break;
357                 case V6:
358                         r = v6lookup(fs, ip, NULL);
359                         break;
360                 default:
361                         panic("arpenter: version %d", version);
362                         return; /* to supress warnings */
363         }
364
365         if (r == NULL) {
366                 return;
367         }
368
369         ifc = r->rt.ifc;
370         type = ifc->m;
371
372         qlock(&arp->qlock);
373         for (a = arp->hash[haship(ip)]; a; a = a->hash) {
374                 if (a->type != type || (a->state != AWAIT && a->state != AOK))
375                         continue;
376
377                 if (ipcmp(a->ip, ip) == 0) {
378                         a->state = AOK;
379                         memmove(a->mac, mac, type->maclen);
380
381                         if (version == V6) {
382                                 /* take out of re-transmit chain */
383                                 l = &arp->rxmt;
384                                 for (f = *l; f; f = f->nextrxt) {
385                                         if (f == a) {
386                                                 *l = a->nextrxt;
387                                                 break;
388                                         }
389                                         l = &f->nextrxt;
390                                 }
391                         }
392
393                         a->ifc = ifc;
394                         a->ifcid = ifc->ifcid;
395                         bp = a->hold;
396                         a->hold = NULL;
397                         if (version == V4)
398                                 ip += IPv4off;
399                         a->utime = NOW;
400                         a->ctime = a->utime;
401                         qunlock(&arp->qlock);
402
403                         while (bp) {
404                                 next = bp->list;
405                                 if (ifc != NULL) {
406                                         rlock(&ifc->rwlock);
407                                         if (waserror()) {
408                                                 runlock(&ifc->rwlock);
409                                                 nexterror();
410                                         }
411                                         if (ifc->m != NULL)
412                                                 ifc->m->bwrite(ifc, bp, version, ip);
413                                         else
414                                                 freeb(bp);
415                                         runlock(&ifc->rwlock);
416                                         poperror();
417                                 } else
418                                         freeb(bp);
419                                 bp = next;
420                         }
421                         return;
422                 }
423         }
424
425         if (refresh == 0) {
426                 a = newarp6(arp, ip, ifc, 0);
427                 a->state = AOK;
428                 a->type = type;
429                 a->ctime = NOW;
430                 memmove(a->mac, mac, type->maclen);
431         }
432
433         qunlock(&arp->qlock);
434 }
435
436 int arpwrite(struct Fs *fs, char *s, long len)
437 {
438         int n;
439         struct route *r;
440         struct arp *arp;
441         struct block *bp;
442         struct arpent *a, *fl, **l;
443         struct medium *m;
444         char *f[4], buf[256];
445         uint8_t ip[IPaddrlen], mac[MAClen];
446
447         arp = fs->arp;
448
449         if (len <= 0)
450                 error(EINVAL, ERROR_FIXME);
451         if (len > sizeof(buf))
452                 len = sizeof(buf);
453         strlcpy(buf, s, sizeof(buf));
454         if (len > 0 && buf[len - 2] == '\n')
455                 buf[len - 2] = 0;
456
457         n = getfields(buf, f, 4, 1, " ");
458         if (strcmp(f[0], "flush") == 0) {
459                 qlock(&arp->qlock);
460                 for (a = arp->cache; a < &arp->cache[NCACHE]; a++) {
461                         memset(a->ip, 0, sizeof(a->ip));
462                         memset(a->mac, 0, sizeof(a->mac));
463                         a->hash = NULL;
464                         a->state = 0;
465                         a->utime = 0;
466                         while (a->hold != NULL) {
467                                 bp = a->hold->list;
468                                 freeblist(a->hold);
469                                 a->hold = bp;
470                         }
471                 }
472                 memset(arp->hash, 0, sizeof(arp->hash));
473                 /* clear all pkts on these lists (rxmt, dropf/l) */
474                 arp->rxmt = NULL;
475                 arp->dropf = NULL;
476                 arp->dropl = NULL;
477                 qunlock(&arp->qlock);
478         } else if (strcmp(f[0], "add") == 0) {
479                 switch (n) {
480                         default:
481                                 error(EINVAL, ERROR_FIXME);
482                         case 3:
483                                 parseip(ip, f[1]);
484                                 if (isv4(ip))
485                                         r = v4lookup(fs, ip + IPv4off, NULL);
486                                 else
487                                         r = v6lookup(fs, ip, NULL);
488                                 if (r == NULL)
489                                         error(EHOSTUNREACH, "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, arpstate[a->state],
579                                a->ip, a->mac);
580                 n += amt;
581                 left -= amt;
582                 qunlock(&arp->qlock);
583         }
584
585         return n;
586 }
587
588 static uint64_t rxmitsols(struct arp *arp)
589 {
590         unsigned int sflag;
591         struct block *next, *xp;
592         struct arpent *a, *b, **l;
593         struct Fs *f;
594         uint8_t ipsrc[IPaddrlen];
595         struct Ipifc *ifc = NULL;
596         uint64_t nrxt;
597
598         qlock(&arp->qlock);
599         f = arp->f;
600
601         a = arp->rxmt;
602         if (a == NULL) {
603                 nrxt = 0;
604                 goto dodrops;   /* return nrxt; */
605         }
606         nrxt = a->rtime - NOW;
607         if (nrxt > 3 * ReTransTimer / 4)
608                 goto dodrops;   /* return nrxt; */
609
610         for (; a; a = a->nextrxt) {
611                 ifc = a->ifc;
612                 assert(ifc != NULL);
613                 if ((a->rxtsrem <= 0) || !(canrlock(&ifc->rwlock))
614                         || (a->ifcid != ifc->ifcid)) {
615                         xp = a->hold;
616                         a->hold = NULL;
617
618                         if (xp) {
619                                 if (arp->dropl == NULL)
620                                         arp->dropf = xp;
621                                 else
622                                         arp->dropl->list = xp;
623                         }
624
625                         cleanarpent(arp, a);
626                 } else
627                         break;
628         }
629         if (a == NULL)
630                 goto dodrops;
631
632         qunlock(&arp->qlock);   /* for icmpns */
633         if ((sflag = ipv6anylocal(ifc, ipsrc)) != SRC_UNSPEC)
634                 icmpns(f, ipsrc, sflag, a->ip, TARG_MULTI, ifc->mac);
635
636         runlock(&ifc->rwlock);
637         qlock(&arp->qlock);
638
639         /* put to the end of re-transmit chain */
640         l = &arp->rxmt;
641         for (b = *l; b; b = b->nextrxt) {
642                 if (b == a) {
643                         *l = a->nextrxt;
644                         break;
645                 }
646                 l = &b->nextrxt;
647         }
648         for (b = *l; b; b = b->nextrxt) {
649                 l = &b->nextrxt;
650         }
651         *l = a;
652         a->rxtsrem--;
653         a->nextrxt = NULL;
654         a->rtime = NOW + ReTransTimer;
655
656         a = arp->rxmt;
657         if (a == NULL)
658                 nrxt = 0;
659         else
660                 nrxt = a->rtime - NOW;
661
662 dodrops:
663         xp = arp->dropf;
664         arp->dropf = NULL;
665         arp->dropl = NULL;
666         qunlock(&arp->qlock);
667
668         for (; xp; xp = next) {
669                 next = xp->list;
670                 icmphostunr(f, ifc, xp, icmp6_adr_unreach, 1);
671         }
672
673         return nrxt;
674
675 }
676
677 static int rxready(void *v)
678 {
679         struct arp *arp = (struct arp *)v;
680         int x;
681
682         x = ((arp->rxmt != NULL) || (arp->dropf != NULL));
683
684         return x;
685 }
686
687 static void rxmitproc(void *v)
688 {
689         ERRSTACK(2);
690         struct arp *arp = v;
691         uint64_t wakeupat;
692
693         arp->rxmitp = current;
694         if (waserror()) {
695                 arp->rxmitp = 0;
696                 poperror();
697                 warn("arp rxmit ktask exited");
698                 return;
699         }
700         for (;;) {
701                 wakeupat = rxmitsols(arp);
702                 if (wakeupat == 0)
703                         rendez_sleep(&arp->rxmtq, rxready, v);
704                 else if (wakeupat > ReTransTimer / 4)
705                         kthread_usleep(wakeupat * 1000);
706         }
707         poperror();
708 }