akaros/kern/src/net/arp.c
<<
>>
Prefs
   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
  45enum {
  46        NHASH = (1 << 6),
  47        NCACHE = 256,
  48
  49        AOK = 1,
  50        AWAIT = 2,
  51};
  52
  53char *arpstate[] = {
  54        "UNUSED",
  55        "OK",
  56        "WAIT",
  57};
  58
  59/*
  60 *  one per Fs
  61 */
  62struct 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
  75int ReTransTimer = RETRANS_TIMER;
  76static void rxmitproc(void *v);
  77
  78void 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 */
  92static 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
 189void 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 */
 230struct 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 */
 288void 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 */
 299struct 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
 331void 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
 435int 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
 548enum {
 549        Alinelen = 90,
 550};
 551
 552static char *aformat = "%-6.6s %-8.8s %-40.40I %E\n";
 553
 554int 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
 589static 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
 663dodrops:
 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
 678static 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
 688static 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}
 710