akaros/kern/src/net/iproute.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
  41static void walkadd(struct Fs *, struct route **, struct route *);
  42static void addnode(struct Fs *, struct route **, struct route *);
  43static void calcd(struct route *);
  44
  45/* these are used for all instances of IP */
  46struct route *v4freelist;
  47struct route *v6freelist;
  48rwlock_t routelock;
  49uint32_t v4routegeneration, v6routegeneration;
  50
  51/*
  52 * TODO: Change this to a proper release.
  53 * At the moment this is difficult to do since deleting
  54 * a route involves manipulating more data structures than
  55 * a kref/struct route.  E.g., unlinking from the route tree
  56 * requires access to a parent pointer, which doesn't exist
  57 * in the route structure itself.
  58 */
  59static void route_release(struct kref *kref)
  60{
  61        (void)kref;
  62}
  63
  64static void freeroute(struct route *r)
  65{
  66        struct route **l;
  67
  68        r->rt.left = NULL;
  69        r->rt.right = NULL;
  70        if (r->rt.type & Rv4)
  71                l = &v4freelist;
  72        else
  73                l = &v6freelist;
  74        r->rt.mid = *l;
  75        *l = r;
  76}
  77
  78static struct route *allocroute(int type)
  79{
  80        struct route *r;
  81        int n;
  82        struct route **l;
  83
  84        if (type & Rv4) {
  85                n = sizeof(struct RouteTree) + sizeof(struct V4route);
  86                l = &v4freelist;
  87        } else {
  88                n = sizeof(struct RouteTree) + sizeof(struct V6route);
  89                l = &v6freelist;
  90        }
  91
  92        r = *l;
  93        if (r != NULL) {
  94                *l = r->rt.mid;
  95        } else {
  96                r = kzmalloc(n, 0);
  97                if (r == NULL)
  98                        panic("out of routing nodes");
  99        }
 100        memset(r, 0, n);
 101        r->rt.type = type;
 102        r->rt.ifc = NULL;
 103        kref_init(&r->rt.kref, route_release, 1);
 104
 105        return r;
 106}
 107
 108static void addqueue(struct route **q, struct route *r)
 109{
 110        struct route *l;
 111
 112        if (r == NULL)
 113                return;
 114
 115        l = allocroute(r->rt.type);
 116        l->rt.mid = *q;
 117        *q = l;
 118        l->rt.left = r;
 119}
 120
 121/*
 122 *   compare 2 v6 addresses
 123 */
 124static int lcmp(uint32_t * a, uint32_t * b)
 125{
 126        int i;
 127
 128        for (i = 0; i < IPllen; i++) {
 129                if (a[i] > b[i])
 130                        return 1;
 131                if (a[i] < b[i])
 132                        return -1;
 133        }
 134        return 0;
 135}
 136
 137/*
 138 *  compare 2 v4 or v6 ranges
 139 */
 140enum {
 141        Rpreceeds,
 142        Rfollows,
 143        Requals,
 144        Rcontains,
 145        Rcontained,
 146};
 147
 148static int rangecompare(struct route *a, struct route *b)
 149{
 150        if (a->rt.type & Rv4) {
 151                if (a->v4.endaddress < b->v4.address)
 152                        return Rpreceeds;
 153
 154                if (a->v4.address > b->v4.endaddress)
 155                        return Rfollows;
 156
 157                if (a->v4.address <= b->v4.address
 158                        && a->v4.endaddress >= b->v4.endaddress) {
 159                        if (a->v4.address == b->v4.address
 160                                && a->v4.endaddress == b->v4.endaddress)
 161                                return Requals;
 162                        return Rcontains;
 163                }
 164                return Rcontained;
 165        }
 166
 167        if (lcmp(a->v6.endaddress, b->v6.address) < 0)
 168                return Rpreceeds;
 169
 170        if (lcmp(a->v6.address, b->v6.endaddress) > 0)
 171                return Rfollows;
 172
 173        if (lcmp(a->v6.address, b->v6.address) <= 0
 174                && lcmp(a->v6.endaddress, b->v6.endaddress) >= 0) {
 175                if (lcmp(a->v6.address, b->v6.address) == 0
 176                        && lcmp(a->v6.endaddress, b->v6.endaddress) == 0)
 177                        return Requals;
 178                return Rcontains;
 179        }
 180
 181        return Rcontained;
 182}
 183
 184static void copygate(struct route *old, struct route *new)
 185{
 186        if (new->rt.type & Rv4)
 187                memmove(old->v4.gate, new->v4.gate, IPv4addrlen);
 188        else
 189                memmove(old->v6.gate, new->v6.gate, IPaddrlen);
 190}
 191
 192/*
 193 *  walk down a tree adding nodes back in
 194 */
 195static void walkadd(struct Fs *f, struct route **root, struct route *p)
 196{
 197        struct route *l, *r;
 198
 199        l = p->rt.left;
 200        r = p->rt.right;
 201        p->rt.left = 0;
 202        p->rt.right = 0;
 203        addnode(f, root, p);
 204        if (l)
 205                walkadd(f, root, l);
 206        if (r)
 207                walkadd(f, root, r);
 208}
 209
 210/*
 211 *  calculate depth
 212 */
 213static void calcd(struct route *p)
 214{
 215        struct route *q;
 216        int d;
 217
 218        if (p) {
 219                d = 0;
 220                q = p->rt.left;
 221                if (q)
 222                        d = q->rt.depth;
 223                q = p->rt.right;
 224                if (q && q->rt.depth > d)
 225                        d = q->rt.depth;
 226                q = p->rt.mid;
 227                if (q && q->rt.depth > d)
 228                        d = q->rt.depth;
 229                p->rt.depth = d + 1;
 230        }
 231}
 232
 233/*
 234 *  balance the tree at the current node
 235 */
 236static void balancetree(struct route **cur)
 237{
 238        struct route *p, *l, *r;
 239        int dl, dr;
 240
 241        /*
 242         * if left and right are
 243         * too out of balance,
 244         * rotate tree node
 245         */
 246        p = *cur;
 247        dl = 0;
 248        if ((l = p->rt.left))
 249                dl = l->rt.depth;
 250        dr = 0;
 251        if ((r = p->rt.right))
 252                dr = r->rt.depth;
 253
 254        if (dl > dr + 1) {
 255                p->rt.left = l->rt.right;
 256                l->rt.right = p;
 257                *cur = l;
 258                calcd(p);
 259                calcd(l);
 260        } else if (dr > dl + 1) {
 261                p->rt.right = r->rt.left;
 262                r->rt.left = p;
 263                *cur = r;
 264                calcd(p);
 265                calcd(r);
 266        } else
 267                calcd(p);
 268}
 269
 270/*
 271 *  add a new node to the tree
 272 */
 273static void addnode(struct Fs *f, struct route **cur, struct route *new)
 274{
 275        struct route *p;
 276
 277        p = *cur;
 278        if (p == 0) {
 279                *cur = new;
 280                new->rt.depth = 1;
 281                return;
 282        }
 283
 284        switch (rangecompare(new, p)) {
 285        case Rpreceeds:
 286                addnode(f, &p->rt.left, new);
 287                break;
 288        case Rfollows:
 289                addnode(f, &p->rt.right, new);
 290                break;
 291        case Rcontains:
 292                /*
 293                 *  if new node is superset
 294                 *  of tree node,
 295                 *  replace tree node and
 296                 *  queue tree node to be
 297                 *  merged into root.
 298                 */
 299                *cur = new;
 300                new->rt.depth = 1;
 301                addqueue(&f->queue, p);
 302                break;
 303        case Requals:
 304                /*
 305                 *  supercede the old entry if the old one isn't
 306                 *  a local interface.
 307                 */
 308                if ((p->rt.type & Rifc) == 0) {
 309                        p->rt.type = new->rt.type;
 310                        p->rt.ifcid = -1;
 311                        copygate(p, new);
 312                } else if (new->rt.type & Rifc)
 313                        kref_get(&p->rt.kref, 1);
 314                freeroute(new);
 315                break;
 316        case Rcontained:
 317                addnode(f, &p->rt.mid, new);
 318                break;
 319        }
 320
 321        balancetree(cur);
 322}
 323
 324#define V4H(a)  ((a&0x07ffffff)>>(32-Lroot-5))
 325
 326void v4addroute(struct Fs *f, char *tag, uint8_t *a, uint8_t *mask,
 327                uint8_t *gate, int type)
 328{
 329        struct route *p;
 330        uint32_t sa;
 331        uint32_t m;
 332        uint32_t ea;
 333        int h, eh;
 334
 335        m = nhgetl(mask);
 336        sa = nhgetl(a) & m;
 337        ea = sa | ~m;
 338
 339        eh = V4H(ea);
 340        for (h = V4H(sa); h <= eh; h++) {
 341                p = allocroute(Rv4 | type);
 342                p->v4.address = sa;
 343                p->v4.endaddress = ea;
 344                memmove(p->v4.gate, gate, sizeof(p->v4.gate));
 345                memmove(p->rt.tag, tag, sizeof(p->rt.tag));
 346
 347                wlock(&routelock);
 348                addnode(f, &f->v4root[h], p);
 349                while ((p = f->queue)) {
 350                        f->queue = p->rt.mid;
 351                        walkadd(f, &f->v4root[h], p->rt.left);
 352                        freeroute(p);
 353                }
 354                wunlock(&routelock);
 355        }
 356        v4routegeneration++;
 357
 358        ipifcaddroute(f, Rv4, a, mask, gate, type);
 359}
 360
 361#define V6H(a)  (((a)[IPllen-1] & 0x07ffffff)>>(32-Lroot-5))
 362#define ISDFLT(a, mask, tag) ((ipcmp((a),v6Unspecified)==0) && (ipcmp((mask),v6Unspecified)==0) && (strcmp((tag), "ra")!=0))
 363
 364void v6addroute(struct Fs *f, char *tag, uint8_t *a, uint8_t *mask,
 365                uint8_t *gate, int type)
 366{
 367        struct route *p;
 368        uint32_t sa[IPllen], ea[IPllen];
 369        uint32_t x, y;
 370        int h, eh;
 371
 372        /*
 373           if(ISDFLT(a, mask, tag))
 374           f->v6p->cdrouter = -1;
 375         */
 376
 377        for (h = 0; h < IPllen; h++) {
 378                x = nhgetl(a + 4 * h);
 379                y = nhgetl(mask + 4 * h);
 380                sa[h] = x & y;
 381                ea[h] = x | ~y;
 382        }
 383
 384        eh = V6H(ea);
 385        for (h = V6H(sa); h <= eh; h++) {
 386                p = allocroute(type);
 387                memmove(p->v6.address, sa, IPaddrlen);
 388                memmove(p->v6.endaddress, ea, IPaddrlen);
 389                memmove(p->v6.gate, gate, IPaddrlen);
 390                memmove(p->rt.tag, tag, sizeof(p->rt.tag));
 391
 392                wlock(&routelock);
 393                addnode(f, &f->v6root[h], p);
 394                while ((p = f->queue)) {
 395                        f->queue = p->rt.mid;
 396                        walkadd(f, &f->v6root[h], p->rt.left);
 397                        freeroute(p);
 398                }
 399                wunlock(&routelock);
 400        }
 401        v6routegeneration++;
 402
 403        ipifcaddroute(f, 0, a, mask, gate, type);
 404}
 405
 406struct route **looknode(struct route **cur, struct route *r)
 407{
 408        struct route *p;
 409
 410        for (;;) {
 411                p = *cur;
 412                if (p == 0)
 413                        return 0;
 414
 415                switch (rangecompare(r, p)) {
 416                case Rcontains:
 417                        return 0;
 418                case Rpreceeds:
 419                        cur = &p->rt.left;
 420                        break;
 421                case Rfollows:
 422                        cur = &p->rt.right;
 423                        break;
 424                case Rcontained:
 425                        cur = &p->rt.mid;
 426                        break;
 427                case Requals:
 428                        return cur;
 429                }
 430        }
 431}
 432
 433void v4delroute(struct Fs *f, uint8_t *a, uint8_t *mask, int dolock)
 434{
 435        struct route **r, *p;
 436        struct route rt;
 437        int h, eh;
 438        uint32_t m;
 439
 440        m = nhgetl(mask);
 441        rt.v4.address = nhgetl(a) & m;
 442        rt.v4.endaddress = rt.v4.address | ~m;
 443        rt.rt.type = Rv4;
 444
 445        eh = V4H(rt.v4.endaddress);
 446        for (h = V4H(rt.v4.address); h <= eh; h++) {
 447                if (dolock)
 448                        wlock(&routelock);
 449                r = looknode(&f->v4root[h], &rt);
 450                if (r) {
 451                        p = *r;
 452                        /* TODO: bad usage of kref (maybe use a release).  I
 453                         * didn't change this one, since it looks like the if
 454                         * code is when we want to release.  btw, use better
 455                         * code reuse btw v4 and v6... */
 456                        if (kref_put(&p->rt.kref)) {
 457                                *r = 0;
 458                                addqueue(&f->queue, p->rt.left);
 459                                addqueue(&f->queue, p->rt.mid);
 460                                addqueue(&f->queue, p->rt.right);
 461                                freeroute(p);
 462                                while ((p = f->queue)) {
 463                                        f->queue = p->rt.mid;
 464                                        walkadd(f, &f->v4root[h], p->rt.left);
 465                                        freeroute(p);
 466                                }
 467                        }
 468                }
 469                if (dolock)
 470                        wunlock(&routelock);
 471        }
 472        v4routegeneration++;
 473
 474        ipifcremroute(f, Rv4, a, mask);
 475}
 476
 477void v6delroute(struct Fs *f, uint8_t * a, uint8_t * mask, int dolock)
 478{
 479        struct route **r, *p;
 480        struct route rt;
 481        int h, eh;
 482        uint32_t x, y;
 483
 484        for (h = 0; h < IPllen; h++) {
 485                x = nhgetl(a + 4 * h);
 486                y = nhgetl(mask + 4 * h);
 487                rt.v6.address[h] = x & y;
 488                rt.v6.endaddress[h] = x | ~y;
 489        }
 490        rt.rt.type = 0;
 491
 492        eh = V6H(rt.v6.endaddress);
 493        for (h = V6H(rt.v6.address); h <= eh; h++) {
 494                if (dolock)
 495                        wlock(&routelock);
 496                r = looknode(&f->v6root[h], &rt);
 497                if (r) {
 498                        p = *r;
 499                        /* TODO: bad usage of kref (maybe use a release).  I
 500                         * didn't change this one, since it looks like the if
 501                         * code is when we want to release.  btw, use better
 502                         * code reuse btw v4 and v6... */
 503                        if (kref_put(&p->rt.kref)) {
 504                                *r = 0;
 505                                addqueue(&f->queue, p->rt.left);
 506                                addqueue(&f->queue, p->rt.mid);
 507                                addqueue(&f->queue, p->rt.right);
 508                                freeroute(p);
 509                                while ((p = f->queue)) {
 510                                        f->queue = p->rt.mid;
 511                                        walkadd(f, &f->v6root[h], p->rt.left);
 512                                        freeroute(p);
 513                                }
 514                        }
 515                }
 516                if (dolock)
 517                        wunlock(&routelock);
 518        }
 519        v6routegeneration++;
 520
 521        ipifcremroute(f, 0, a, mask);
 522}
 523
 524struct route *v4lookup(struct Fs *f, uint8_t * a, struct conv *c)
 525{
 526        struct route *p, *q;
 527        uint32_t la;
 528        uint8_t gate[IPaddrlen];
 529        struct Ipifc *ifc;
 530
 531        if (c != NULL && c->r != NULL && c->r->rt.ifc != NULL
 532                && c->rgen == v4routegeneration)
 533                return c->r;
 534
 535        la = nhgetl(a);
 536        q = NULL;
 537        for (p = f->v4root[V4H(la)]; p;)
 538                if (la >= p->v4.address) {
 539                        if (la <= p->v4.endaddress) {
 540                                q = p;
 541                                p = p->rt.mid;
 542                        } else
 543                                p = p->rt.right;
 544                } else
 545                        p = p->rt.left;
 546
 547        if (q && (q->rt.ifc == NULL || q->rt.ifcid != q->rt.ifc->ifcid)) {
 548                if (q->rt.type & Rifc) {
 549                        hnputl(gate + IPv4off, q->v4.address);
 550                        memmove(gate, v4prefix, IPv4off);
 551                } else
 552                        v4tov6(gate, q->v4.gate);
 553                ifc = findipifc(f, gate, q->rt.type);
 554                if (ifc == NULL)
 555                        return NULL;
 556                q->rt.ifc = ifc;
 557                q->rt.ifcid = ifc->ifcid;
 558        }
 559
 560        if (c != NULL) {
 561                c->r = q;
 562                c->rgen = v4routegeneration;
 563        }
 564
 565        return q;
 566}
 567
 568struct route *v6lookup(struct Fs *f, uint8_t * a, struct conv *c)
 569{
 570        struct route *p, *q;
 571        uint32_t la[IPllen];
 572        int h;
 573        uint32_t x, y;
 574        uint8_t gate[IPaddrlen];
 575        struct Ipifc *ifc;
 576
 577        if (memcmp(a, v4prefix, IPv4off) == 0) {
 578                q = v4lookup(f, a + IPv4off, c);
 579                if (q != NULL)
 580                        return q;
 581        }
 582
 583        if (c != NULL && c->r != NULL && c->r->rt.ifc != NULL
 584                && c->rgen == v6routegeneration)
 585                return c->r;
 586
 587        for (h = 0; h < IPllen; h++)
 588                la[h] = nhgetl(a + 4 * h);
 589
 590        q = 0;
 591        for (p = f->v6root[V6H(la)]; p;) {
 592                for (h = 0; h < IPllen; h++) {
 593                        x = la[h];
 594                        y = p->v6.address[h];
 595                        if (x == y)
 596                                continue;
 597                        if (x < y) {
 598                                p = p->rt.left;
 599                                goto next;
 600                        }
 601                        break;
 602                }
 603                for (h = 0; h < IPllen; h++) {
 604                        x = la[h];
 605                        y = p->v6.endaddress[h];
 606                        if (x == y)
 607                                continue;
 608                        if (x > y) {
 609                                p = p->rt.right;
 610                                goto next;
 611                        }
 612                        break;
 613                }
 614                q = p;
 615                p = p->rt.mid;
 616next:   ;
 617        }
 618
 619        if (q && (q->rt.ifc == NULL || q->rt.ifcid != q->rt.ifc->ifcid)) {
 620                if (q->rt.type & Rifc) {
 621                        for (h = 0; h < IPllen; h++)
 622                                hnputl(gate + 4 * h, q->v6.address[h]);
 623                        ifc = findipifc(f, gate, q->rt.type);
 624                } else
 625                        ifc = findipifc(f, q->v6.gate, q->rt.type);
 626                if (ifc == NULL)
 627                        return NULL;
 628                q->rt.ifc = ifc;
 629                q->rt.ifcid = ifc->ifcid;
 630        }
 631        if (c != NULL) {
 632                c->r = q;
 633                c->rgen = v6routegeneration;
 634        }
 635
 636        return q;
 637}
 638
 639void routetype(int type, char *p)
 640{
 641        memset(p, ' ', 4);
 642        p[4] = 0;
 643        if (type & Rv4)
 644                *p++ = '4';
 645        else
 646                *p++ = '6';
 647        if (type & Rifc)
 648                *p++ = 'i';
 649        if (type & Runi)
 650                *p++ = 'u';
 651        else if (type & Rbcast)
 652                *p++ = 'b';
 653        else if (type & Rmulti)
 654                *p++ = 'm';
 655        if (type & Rptpt)
 656                *p = 'p';
 657}
 658
 659char *rformat = "%-15I %-4M %-15I %4.4s %4.4s %3s\n";
 660
 661void convroute(struct route *r, uint8_t *addr, uint8_t *mask, uint8_t *gate,
 662               char *t, int *nifc)
 663{
 664        int i;
 665
 666        if (r->rt.type & Rv4) {
 667                memmove(addr, v4prefix, IPv4off);
 668                hnputl(addr + IPv4off, r->v4.address);
 669                memset(mask, 0xff, IPv4off);
 670                hnputl(mask + IPv4off, ~(r->v4.endaddress ^ r->v4.address));
 671                memmove(gate, v4prefix, IPv4off);
 672                memmove(gate + IPv4off, r->v4.gate, IPv4addrlen);
 673        } else {
 674                for (i = 0; i < IPllen; i++) {
 675                        hnputl(addr + 4 * i, r->v6.address[i]);
 676                        hnputl(mask + 4 * i,
 677                               ~(r->v6.endaddress[i] ^ r->v6.address[i]));
 678                }
 679                memmove(gate, r->v6.gate, IPaddrlen);
 680        }
 681
 682        routetype(r->rt.type, t);
 683
 684        if (r->rt.ifc)
 685                *nifc = r->rt.ifc->conv->x;
 686        else
 687                *nifc = -1;
 688}
 689
 690/*
 691 *  this code is not in rr to reduce stack size
 692 */
 693static void sprintroute(struct route *r, struct routewalk *rw)
 694{
 695        int nifc, n;
 696        char t[5], *iname, ifbuf[5];
 697        uint8_t addr[IPaddrlen], mask[IPaddrlen], gate[IPaddrlen];
 698        char *p;
 699
 700        convroute(r, addr, mask, gate, t, &nifc);
 701        iname = "-";
 702        if (nifc != -1) {
 703                iname = ifbuf;
 704                snprintf(ifbuf, sizeof ifbuf, "%d", nifc);
 705        }
 706        p = seprintf(rw->p, rw->e, rformat, addr, mask, gate, t, r->rt.tag,
 707                     iname);
 708        if (rw->o < 0) {
 709                n = p - rw->p;
 710                if (n > -rw->o) {
 711                        memmove(rw->p, rw->p - rw->o, n + rw->o);
 712                        rw->p = p + rw->o;
 713                }
 714                rw->o += n;
 715        } else
 716                rw->p = p;
 717}
 718
 719/*
 720 *  recurse descending tree, applying the function in Routewalk
 721 */
 722static int rr(struct route *r, struct routewalk *rw)
 723{
 724        int h;
 725
 726        if (rw->e <= rw->p)
 727                return 0;
 728        if (r == NULL)
 729                return 1;
 730
 731        if (rr(r->rt.left, rw) == 0)
 732                return 0;
 733
 734        if (r->rt.type & Rv4)
 735                h = V4H(r->v4.address);
 736        else
 737                h = V6H(r->v6.address);
 738
 739        if (h == rw->h)
 740                rw->walk(r, rw);
 741
 742        if (rr(r->rt.mid, rw) == 0)
 743                return 0;
 744
 745        return rr(r->rt.right, rw);
 746}
 747
 748void ipwalkroutes(struct Fs *f, struct routewalk *rw)
 749{
 750        rlock(&routelock);
 751        if (rw->e > rw->p) {
 752                for (rw->h = 0; rw->h < ARRAY_SIZE(f->v4root); rw->h++)
 753                        if (rr(f->v4root[rw->h], rw) == 0)
 754                                break;
 755        }
 756        if (rw->e > rw->p) {
 757                for (rw->h = 0; rw->h < ARRAY_SIZE(f->v6root); rw->h++)
 758                        if (rr(f->v6root[rw->h], rw) == 0)
 759                                break;
 760        }
 761        runlock(&routelock);
 762}
 763
 764long routeread(struct Fs *f, char *p, uint32_t offset, int n)
 765{
 766        struct routewalk rw;
 767
 768        rw.p = p;
 769        rw.e = p + n;
 770        rw.o = -offset;
 771        rw.walk = sprintroute;
 772
 773        ipwalkroutes(f, &rw);
 774
 775        return rw.p - p;
 776}
 777
 778/*
 779 *  this code is not in routeflush to reduce stack size
 780 */
 781void delroute(struct Fs *f, struct route *r, int dolock)
 782{
 783        uint8_t addr[IPaddrlen];
 784        uint8_t mask[IPaddrlen];
 785        uint8_t gate[IPaddrlen];
 786        char t[5];
 787        int nifc;
 788
 789        convroute(r, addr, mask, gate, t, &nifc);
 790        if (r->rt.type & Rv4)
 791                v4delroute(f, addr + IPv4off, mask + IPv4off, dolock);
 792        else
 793                v6delroute(f, addr, mask, dolock);
 794}
 795
 796/*
 797 *  recurse until one route is deleted
 798 *    returns 0 if nothing is deleted, 1 otherwise
 799 */
 800int routeflush(struct Fs *f, struct route *r, char *tag)
 801{
 802        if (r == NULL)
 803                return 0;
 804        if (routeflush(f, r->rt.mid, tag))
 805                return 1;
 806        if (routeflush(f, r->rt.left, tag))
 807                return 1;
 808        if (routeflush(f, r->rt.right, tag))
 809                return 1;
 810        if ((r->rt.type & Rifc) == 0) {
 811                if (tag == NULL ||
 812                    strncmp(tag, r->rt.tag, sizeof(r->rt.tag)) == 0) {
 813                        delroute(f, r, 0);
 814                        return 1;
 815                }
 816        }
 817        return 0;
 818}
 819
 820long routewrite(struct Fs *f, struct chan *c, char *p, size_t n)
 821{
 822        ERRSTACK(1);
 823        int h, changed;
 824        char *tag;
 825        struct cmdbuf *cb;
 826        uint8_t addr[IPaddrlen];
 827        uint8_t mask[IPaddrlen];
 828        uint8_t gate[IPaddrlen];
 829        struct IPaux *a, *na;
 830
 831        cb = parsecmd(p, n);
 832        if (waserror()) {
 833                kfree(cb);
 834                nexterror();
 835        }
 836        if (cb->nf < 1)
 837                error(EINVAL, "short control request");
 838
 839        if (strcmp(cb->f[0], "flush") == 0) {
 840                tag = cb->f[1];
 841                for (h = 0; h < ARRAY_SIZE(f->v4root); h++)
 842                        for (changed = 1; changed;) {
 843                                wlock(&routelock);
 844                                changed = routeflush(f, f->v4root[h], tag);
 845                                wunlock(&routelock);
 846                        }
 847                for (h = 0; h < ARRAY_SIZE(f->v6root); h++)
 848                        for (changed = 1; changed;) {
 849                                wlock(&routelock);
 850                                changed = routeflush(f, f->v6root[h], tag);
 851                                wunlock(&routelock);
 852                        }
 853        } else if (strcmp(cb->f[0], "remove") == 0) {
 854                if (cb->nf < 3)
 855                        error(EINVAL, ERROR_FIXME);
 856                parseip(addr, cb->f[1]);
 857                parseipmask(mask, cb->f[2]);
 858                if (memcmp(addr, v4prefix, IPv4off) == 0)
 859                        v4delroute(f, addr + IPv4off, mask + IPv4off, 1);
 860                else
 861                        v6delroute(f, addr, mask, 1);
 862        } else if (strcmp(cb->f[0], "add") == 0) {
 863                if (cb->nf < 4)
 864                        error(EINVAL, ERROR_FIXME);
 865                parseip(addr, cb->f[1]);
 866                parseipmask(mask, cb->f[2]);
 867                parseip(gate, cb->f[3]);
 868                tag = "none";
 869                if (c != NULL) {
 870                        a = c->aux;
 871                        tag = a->tag;
 872                }
 873                if (memcmp(addr, v4prefix, IPv4off) == 0)
 874                        v4addroute(f, tag, addr + IPv4off, mask + IPv4off,
 875                                   gate + IPv4off, 0);
 876                else
 877                        v6addroute(f, tag, addr, mask, gate, 0);
 878        } else if (strcmp(cb->f[0], "tag") == 0) {
 879                if (cb->nf < 2)
 880                        error(EINVAL, ERROR_FIXME);
 881
 882                a = c->aux;
 883                na = newipaux(a->owner, cb->f[1]);
 884                c->aux = na;
 885                kfree(a);
 886        }
 887
 888        poperror();
 889        kfree(cb);
 890        return n;
 891}
 892