sys/net/route.c

   1 /*
   2  * Copyright (c) 2004, 2005 The DragonFly Project.  All rights reserved.
   3  *
   4  * This code is derived from software contributed to The DragonFly Project
   5  * by Jeffrey M. Hsu.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of The DragonFly Project nor the names of its
  16  *    contributors may be used to endorse or promote products derived
  17  *    from this software without specific, prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  21  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  22  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
  23  * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  24  * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
  25  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  26  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
  27  * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  28  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  29  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 /*
  34  * Copyright (c) 1980, 1986, 1991, 1993
  35  *      The Regents of the University of California.  All rights reserved.
  36  *
  37  * Redistribution and use in source and binary forms, with or without
  38  * modification, are permitted provided that the following conditions
  39  * are met:
  40  * 1. Redistributions of source code must retain the above copyright
  41  *    notice, this list of conditions and the following disclaimer.
  42  * 2. Redistributions in binary form must reproduce the above copyright
  43  *    notice, this list of conditions and the following disclaimer in the
  44  *    documentation and/or other materials provided with the distribution.
  45  * 4. Neither the name of the University nor the names of its contributors
  46  *    may be used to endorse or promote products derived from this software
  47  *    without specific prior written permission.
  48  *
  49  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  50  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  51  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  52  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  53  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  54  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  55  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  56  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  57  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  58  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  59  * SUCH DAMAGE.
  60  *
  61  *      @(#)route.c     8.3 (Berkeley) 1/9/95
  62  * $FreeBSD: src/sys/net/route.c,v 1.59.2.10 2003/01/17 08:04:00 ru Exp $
  63  */
  64
  65 #include "opt_inet.h"
  66 #include "opt_mpls.h"
  67
  68 #include <sys/param.h>
  69 #include <sys/systm.h>
  70 #include <sys/malloc.h>
  71 #include <sys/mbuf.h>
  72 #include <sys/socket.h>
  73 #include <sys/domain.h>
  74 #include <sys/kernel.h>
  75 #include <sys/sysctl.h>
  76 #include <sys/globaldata.h>
  77 #include <sys/thread.h>
  78
  79 #include <net/if.h>
  80 #include <net/route.h>
  81 #include <net/netisr.h>
  82
  83 #include <netinet/in.h>
  84 #include <net/ip_mroute/ip_mroute.h>
  85
  86 #include <sys/thread2.h>
  87 #include <sys/msgport2.h>
  88 #include <net/netmsg2.h>
  89
  90 #ifdef MPLS
  91 #include <netproto/mpls/mpls.h>
  92 #endif
  93
  94 static struct rtstatistics rtstatistics_percpu[MAXCPU];
  95 #define rtstat  rtstatistics_percpu[mycpuid]
  96
  97 struct radix_node_head *rt_tables[MAXCPU][AF_MAX+1];
  98 struct lwkt_port *rt_ports[MAXCPU];
  99
 100 static void     rt_maskedcopy (struct sockaddr *, struct sockaddr *,
 101                                struct sockaddr *);
 102 static void rtable_init(void);
 103 static void rtable_service_loop(void *dummy);
 104 static void rtinit_rtrequest_callback(int, int, struct rt_addrinfo *,
 105                                       struct rtentry *, void *);
 106
 107 static void rtredirect_msghandler(netmsg_t msg);
 108 static void rtrequest1_msghandler(netmsg_t msg);
 109 static void rtsearch_msghandler(netmsg_t msg);
 110 static void rtmask_add_msghandler(netmsg_t msg);
 111
 112 static int rt_setshims(struct rtentry *, struct sockaddr **);
 113
 114 SYSCTL_NODE(_net, OID_AUTO, route, CTLFLAG_RW, 0, "Routing");
 115
 116 #ifdef ROUTE_DEBUG
 117 static int route_debug = 1;
 118 SYSCTL_INT(_net_route, OID_AUTO, route_debug, CTLFLAG_RW,
 119            &route_debug, 0, "");
 120 #endif
 121
 122 int route_assert_owner_access = 1;
 123 SYSCTL_INT(_net_route, OID_AUTO, assert_owner_access, CTLFLAG_RW,
 124            &route_assert_owner_access, 0, "");
 125
 126 u_long route_kmalloc_limit = 0;
 127 TUNABLE_ULONG("net.route.kmalloc_limit", &route_kmalloc_limit);
 128
 129 /*
 130  * Initialize the route table(s) for protocol domains and
 131  * create a helper thread which will be responsible for updating
 132  * route table entries on each cpu.
 133  */
 134 void
 135 route_init(void)
 136 {
 137         int cpu;
 138         thread_t rtd;
 139
 140         for (cpu = 0; cpu < ncpus; ++cpu)
 141                 bzero(&rtstatistics_percpu[cpu], sizeof(struct rtstatistics));
 142         rn_init();      /* initialize all zeroes, all ones, mask table */
 143         rtable_init();  /* call dom_rtattach() on each cpu */
 144
 145         for (cpu = 0; cpu < ncpus; cpu++) {
 146                 lwkt_create(rtable_service_loop, NULL, &rtd, NULL,
 147                             0, cpu, "rtable_cpu %d", cpu);
 148                 rt_ports[cpu] = &rtd->td_msgport;
 149         }
 150
 151         if (route_kmalloc_limit)
 152                 kmalloc_raise_limit(M_RTABLE, route_kmalloc_limit);
 153 }
 154
 155 static void
 156 rtable_init_oncpu(netmsg_t msg)
 157 {
 158         struct domain *dom;
 159         int cpu = mycpuid;
 160
 161         SLIST_FOREACH(dom, &domains, dom_next) {
 162                 if (dom->dom_rtattach) {
 163                         dom->dom_rtattach(
 164                                 (void **)&rt_tables[cpu][dom->dom_family],
 165                                 dom->dom_rtoffset);
 166                 }
 167         }
 168         ifnet_forwardmsg(&msg->lmsg, cpu + 1);
 169 }
 170
 171 static void
 172 rtable_init(void)
 173 {
 174         struct netmsg_base msg;
 175
 176         netmsg_init(&msg, NULL, &curthread->td_msgport, 0, rtable_init_oncpu);
 177         ifnet_domsg(&msg.lmsg, 0);
 178 }
 179
 180 /*
 181  * Our per-cpu table management protocol thread.  All route table operations
 182  * are sequentially chained through all cpus starting at cpu #0 in order to
 183  * maintain duplicate route tables on each cpu.  Having a spearate route
 184  * table management thread allows the protocol and interrupt threads to
 185  * issue route table changes.
 186  */
 187 static void
 188 rtable_service_loop(void *dummy __unused)
 189 {
 190         netmsg_base_t msg;
 191         thread_t td = curthread;
 192
 193         while ((msg = lwkt_waitport(&td->td_msgport, 0)) != NULL) {
 194                 msg->nm_dispatch((netmsg_t)msg);
 195         }
 196 }
 197
 198 /*
 199  * Routing statistics.
 200  */
 201 static int
 202 sysctl_rtstatistics(SYSCTL_HANDLER_ARGS)
 203 {
 204         int cpu, error = 0;
 205
 206         for (cpu = 0; cpu < ncpus; ++cpu) {
 207                 if ((error = SYSCTL_OUT(req, &rtstatistics_percpu[cpu],
 208                                         sizeof(struct rtstatistics))))
 209                                 break;
 210                 if ((error = SYSCTL_IN(req, &rtstatistics_percpu[cpu],
 211                                         sizeof(struct rtstatistics))))
 212                                 break;
 213         }
 214
 215         return (error);
 216 }
 217 SYSCTL_PROC(_net_route, OID_AUTO, stats, (CTLTYPE_OPAQUE|CTLFLAG_RW),
 218         0, 0, sysctl_rtstatistics, "S,rtstatistics", "Routing statistics");
 219
 220 /*
 221  * Packet routing routines.
 222  */
 223
 224 /*
 225  * Look up and fill in the "ro_rt" rtentry field in a route structure given
 226  * an address in the "ro_dst" field.  Always send a report on a miss and
 227  * always clone routes.
 228  */
 229 void
 230 rtalloc(struct route *ro)
 231 {
 232         rtalloc_ign(ro, 0UL);
 233 }
 234
 235 /*
 236  * Look up and fill in the "ro_rt" rtentry field in a route structure given
 237  * an address in the "ro_dst" field.  Always send a report on a miss and
 238  * optionally clone routes when RTF_CLONING or RTF_PRCLONING are not being
 239  * ignored.
 240  */
 241 void
 242 rtalloc_ign(struct route *ro, u_long ignoreflags)
 243 {
 244         if (ro->ro_rt != NULL) {
 245                 if (ro->ro_rt->rt_ifp != NULL && ro->ro_rt->rt_flags & RTF_UP)
 246                         return;
 247                 rtfree(ro->ro_rt);
 248                 ro->ro_rt = NULL;
 249         }
 250         ro->ro_rt = _rtlookup(&ro->ro_dst, RTL_REPORTMSG, ignoreflags);
 251 }
 252
 253 /*
 254  * Look up the route that matches the given "dst" address.
 255  *
 256  * Route lookup can have the side-effect of creating and returning
 257  * a cloned route instead when "dst" matches a cloning route and the
 258  * RTF_CLONING and RTF_PRCLONING flags are not being ignored.
 259  *
 260  * Any route returned has its reference count incremented.
 261  */
 262 struct rtentry *
 263 _rtlookup(struct sockaddr *dst, boolean_t generate_report, u_long ignore)
 264 {
 265         struct radix_node_head *rnh = rt_tables[mycpuid][dst->sa_family];
 266         struct rtentry *rt;
 267
 268         if (rnh == NULL)
 269                 goto unreach;
 270
 271         /*
 272          * Look up route in the radix tree.
 273          */
 274         rt = (struct rtentry *) rnh->rnh_matchaddr((char *)dst, rnh);
 275         if (rt == NULL)
 276                 goto unreach;
 277
 278         /*
 279          * Handle cloning routes.
 280          */
 281         if ((rt->rt_flags & ~ignore & (RTF_CLONING | RTF_PRCLONING)) != 0) {
 282                 struct rtentry *clonedroute;
 283                 int error;
 284
 285                 clonedroute = rt;       /* copy in/copy out parameter */
 286                 error = rtrequest(RTM_RESOLVE, dst, NULL, NULL, 0,
 287                                   &clonedroute);        /* clone the route */
 288                 if (error != 0) {       /* cloning failed */
 289                         if (generate_report)
 290                                 rt_dstmsg(RTM_MISS, dst, error);
 291                         rt->rt_refcnt++;
 292                         return (rt);    /* return the uncloned route */
 293                 }
 294                 if (generate_report) {
 295                         if (clonedroute->rt_flags & RTF_XRESOLVE)
 296                                 rt_dstmsg(RTM_RESOLVE, dst, 0);
 297                         else
 298                                 rt_rtmsg(RTM_ADD, clonedroute,
 299                                          clonedroute->rt_ifp, 0);
 300                 }
 301                 return (clonedroute);   /* return cloned route */
 302         }
 303
 304         /*
 305          * Increment the reference count of the matched route and return.
 306          */
 307         rt->rt_refcnt++;
 308         return (rt);
 309
 310 unreach:
 311         rtstat.rts_unreach++;
 312         if (generate_report)
 313                 rt_dstmsg(RTM_MISS, dst, 0);
 314         return (NULL);
 315 }
 316
 317 void
 318 rtfree(struct rtentry *rt)
 319 {
 320         if (rt->rt_cpuid == mycpuid)
 321                 rtfree_oncpu(rt);
 322         else
 323                 rtfree_remote(rt);
 324 }
 325
 326 void
 327 rtfree_oncpu(struct rtentry *rt)
 328 {
 329         KKASSERT(rt->rt_cpuid == mycpuid);
 330         KASSERT(rt->rt_refcnt > 0, ("rtfree: rt_refcnt %ld", rt->rt_refcnt));
 331
 332         --rt->rt_refcnt;
 333         if (rt->rt_refcnt == 0) {
 334                 struct radix_node_head *rnh =
 335                     rt_tables[mycpuid][rt_key(rt)->sa_family];
 336
 337                 if (rnh->rnh_close)
 338                         rnh->rnh_close((struct radix_node *)rt, rnh);
 339                 if (!(rt->rt_flags & RTF_UP)) {
 340                         /* deallocate route */
 341                         if (rt->rt_ifa != NULL)
 342                                 IFAFREE(rt->rt_ifa);
 343                         if (rt->rt_parent != NULL)
 344                                 RTFREE(rt->rt_parent);  /* recursive call! */
 345                         Free(rt_key(rt));
 346                         Free(rt);
 347                 }
 348         }
 349 }
 350
 351 static void
 352 rtfree_remote_dispatch(netmsg_t msg)
 353 {
 354         struct lwkt_msg *lmsg = &msg->lmsg;
 355         struct rtentry *rt = lmsg->u.ms_resultp;
 356
 357         rtfree_oncpu(rt);
 358         lwkt_replymsg(lmsg, 0);
 359 }
 360
 361 void
 362 rtfree_remote(struct rtentry *rt)
 363 {
 364         struct netmsg_base msg;
 365         struct lwkt_msg *lmsg;
 366
 367         KKASSERT(rt->rt_cpuid != mycpuid);
 368
 369         if (route_assert_owner_access) {
 370                 panic("rt remote free rt_cpuid %d, mycpuid %d",
 371                       rt->rt_cpuid, mycpuid);
 372         } else {
 373                 kprintf("rt remote free rt_cpuid %d, mycpuid %d\n",
 374                         rt->rt_cpuid, mycpuid);
 375                 print_backtrace(-1);
 376         }
 377
 378         netmsg_init(&msg, NULL, &curthread->td_msgport,
 379                     0, rtfree_remote_dispatch);
 380         lmsg = &msg.lmsg;
 381         lmsg->u.ms_resultp = rt;
 382
 383         lwkt_domsg(rtable_portfn(rt->rt_cpuid), lmsg, 0);
 384 }
 385
 386 static int
 387 rtredirect_oncpu(struct sockaddr *dst, struct sockaddr *gateway,
 388                  struct sockaddr *netmask, int flags, struct sockaddr *src)
 389 {
 390         struct rtentry *rt = NULL;
 391         struct rt_addrinfo rtinfo;
 392         struct ifaddr *ifa;
 393         u_long *stat = NULL;
 394         int error;
 395
 396         /* verify the gateway is directly reachable */
 397         if ((ifa = ifa_ifwithnet(gateway)) == NULL) {
 398                 error = ENETUNREACH;
 399                 goto out;
 400         }
 401
 402         /*
 403          * If the redirect isn't from our current router for this destination,
 404          * it's either old or wrong.
 405          */
 406         if (!(flags & RTF_DONE) &&              /* XXX JH */
 407             (rt = rtpurelookup(dst)) != NULL &&
 408             (!sa_equal(src, rt->rt_gateway) || rt->rt_ifa != ifa)) {
 409                 error = EINVAL;
 410                 goto done;
 411         }
 412
 413         /*
 414          * If it redirects us to ourselves, we have a routing loop,
 415          * perhaps as a result of an interface going down recently.
 416          */
 417         if (ifa_ifwithaddr(gateway)) {
 418                 error = EHOSTUNREACH;
 419                 goto done;
 420         }
 421
 422         /*
 423          * Create a new entry if the lookup failed or if we got back
 424          * a wildcard entry for the default route.  This is necessary
 425          * for hosts which use routing redirects generated by smart
 426          * gateways to dynamically build the routing tables.
 427          */
 428         if (rt == NULL)
 429                 goto create;
 430         if ((rt_mask(rt) != NULL && rt_mask(rt)->sa_len < 2)) {
 431                 rtfree(rt);
 432                 goto create;
 433         }
 434
 435         /* Ignore redirects for directly connected hosts. */
 436         if (!(rt->rt_flags & RTF_GATEWAY)) {
 437                 error = EHOSTUNREACH;
 438                 goto done;
 439         }
 440
 441         if (!(rt->rt_flags & RTF_HOST) && (flags & RTF_HOST)) {
 442                 /*
 443                  * Changing from a network route to a host route.
 444                  * Create a new host route rather than smashing the
 445                  * network route.
 446                  */
 447 create:
 448                 flags |=  RTF_GATEWAY | RTF_DYNAMIC;
 449                 bzero(&rtinfo, sizeof(struct rt_addrinfo));
 450                 rtinfo.rti_info[RTAX_DST] = dst;
 451                 rtinfo.rti_info[RTAX_GATEWAY] = gateway;
 452                 rtinfo.rti_info[RTAX_NETMASK] = netmask;
 453                 rtinfo.rti_flags = flags;
 454                 rtinfo.rti_ifa = ifa;
 455                 rt = NULL;      /* copy-in/copy-out parameter */
 456                 error = rtrequest1(RTM_ADD, &rtinfo, &rt);
 457                 if (rt != NULL)
 458                         flags = rt->rt_flags;
 459                 stat = &rtstat.rts_dynamic;
 460         } else {
 461                 /*
 462                  * Smash the current notion of the gateway to this destination.
 463                  * Should check about netmask!!!
 464                  */
 465                 rt->rt_flags |= RTF_MODIFIED;
 466                 flags |= RTF_MODIFIED;
 467
 468                 /* We only need to report rtmsg on CPU0 */
 469                 rt_setgate(rt, rt_key(rt), gateway,
 470                            mycpuid == 0 ? RTL_REPORTMSG : RTL_DONTREPORT);
 471                 error = 0;
 472                 stat = &rtstat.rts_newgateway;
 473         }
 474
 475 done:
 476         if (rt != NULL)
 477                 rtfree(rt);
 478 out:
 479         if (error != 0)
 480                 rtstat.rts_badredirect++;
 481         else if (stat != NULL)
 482                 (*stat)++;
 483
 484         return error;
 485 }
 486
 487 struct netmsg_rtredirect {
 488         struct netmsg_base base;
 489         struct sockaddr *dst;
 490         struct sockaddr *gateway;
 491         struct sockaddr *netmask;
 492         int             flags;
 493         struct sockaddr *src;
 494 };
 495
 496 /*
 497  * Force a routing table entry to the specified
 498  * destination to go through the given gateway.
 499  * Normally called as a result of a routing redirect
 500  * message from the network layer.
 501  *
 502  * N.B.: must be called at splnet
 503  */
 504 void
 505 rtredirect(struct sockaddr *dst, struct sockaddr *gateway,
 506            struct sockaddr *netmask, int flags, struct sockaddr *src)
 507 {
 508         struct rt_addrinfo rtinfo;
 509         int error;
 510         struct netmsg_rtredirect msg;
 511
 512         netmsg_init(&msg.base, NULL, &curthread->td_msgport,
 513                     0, rtredirect_msghandler);
 514         msg.dst = dst;
 515         msg.gateway = gateway;
 516         msg.netmask = netmask;
 517         msg.flags = flags;
 518         msg.src = src;
 519         error = lwkt_domsg(rtable_portfn(0), &msg.base.lmsg, 0);
 520         bzero(&rtinfo, sizeof(struct rt_addrinfo));
 521         rtinfo.rti_info[RTAX_DST] = dst;
 522         rtinfo.rti_info[RTAX_GATEWAY] = gateway;
 523         rtinfo.rti_info[RTAX_NETMASK] = netmask;
 524         rtinfo.rti_info[RTAX_AUTHOR] = src;
 525         rt_missmsg(RTM_REDIRECT, &rtinfo, flags, error);
 526 }
 527
 528 static void
 529 rtredirect_msghandler(netmsg_t msg)
 530 {
 531         struct netmsg_rtredirect *rmsg = (void *)msg;
 532         int nextcpu;
 533
 534         rtredirect_oncpu(rmsg->dst, rmsg->gateway, rmsg->netmask,
 535                          rmsg->flags, rmsg->src);
 536         nextcpu = mycpuid + 1;
 537         if (nextcpu < ncpus)
 538                 lwkt_forwardmsg(rtable_portfn(nextcpu), &msg->lmsg);
 539         else
 540                 lwkt_replymsg(&msg->lmsg, 0);
 541 }
 542
 543 /*
 544 * Routing table ioctl interface.
 545 */
 546 int
 547 rtioctl(u_long req, caddr_t data, struct ucred *cred)
 548 {
 549 #ifdef INET
 550         /* Multicast goop, grrr... */
 551         return mrt_ioctl ? mrt_ioctl(req, data) : EOPNOTSUPP;
 552 #else
 553         return ENXIO;
 554 #endif
 555 }
 556
 557 struct ifaddr *
 558 ifa_ifwithroute(int flags, struct sockaddr *dst, struct sockaddr *gateway)
 559 {
 560         struct ifaddr *ifa;
 561
 562         if (!(flags & RTF_GATEWAY)) {
 563                 /*
 564                  * If we are adding a route to an interface,
 565                  * and the interface is a point-to-point link,
 566                  * we should search for the destination
 567                  * as our clue to the interface.  Otherwise
 568                  * we can use the local address.
 569                  */
 570                 ifa = NULL;
 571                 if (flags & RTF_HOST) {
 572                         ifa = ifa_ifwithdstaddr(dst);
 573                 }
 574                 if (ifa == NULL)
 575                         ifa = ifa_ifwithaddr(gateway);
 576         } else {
 577                 /*
 578                  * If we are adding a route to a remote net
 579                  * or host, the gateway may still be on the
 580                  * other end of a pt to pt link.
 581                  */
 582                 ifa = ifa_ifwithdstaddr(gateway);
 583         }
 584         if (ifa == NULL)
 585                 ifa = ifa_ifwithnet(gateway);
 586         if (ifa == NULL) {
 587                 struct rtentry *rt;
 588
 589                 rt = rtpurelookup(gateway);
 590                 if (rt == NULL)
 591                         return (NULL);
 592                 rt->rt_refcnt--;
 593                 if ((ifa = rt->rt_ifa) == NULL)
 594                         return (NULL);
 595         }
 596         if (ifa->ifa_addr->sa_family != dst->sa_family) {
 597                 struct ifaddr *oldifa = ifa;
 598
 599                 ifa = ifaof_ifpforaddr(dst, ifa->ifa_ifp);
 600                 if (ifa == NULL)
 601                         ifa = oldifa;
 602         }
 603         return (ifa);
 604 }
 605
 606 static int rt_fixdelete (struct radix_node *, void *);
 607 static int rt_fixchange (struct radix_node *, void *);
 608
 609 struct rtfc_arg {
 610         struct rtentry *rt0;
 611         struct radix_node_head *rnh;
 612 };
 613
 614 /*
 615  * Set rtinfo->rti_ifa and rtinfo->rti_ifp.
 616  */
 617 int
 618 rt_getifa(struct rt_addrinfo *rtinfo)
 619 {
 620         struct sockaddr *gateway = rtinfo->rti_info[RTAX_GATEWAY];
 621         struct sockaddr *dst = rtinfo->rti_info[RTAX_DST];
 622         struct sockaddr *ifaaddr = rtinfo->rti_info[RTAX_IFA];
 623         int flags = rtinfo->rti_flags;
 624
 625         /*
 626          * ifp may be specified by sockaddr_dl
 627          * when protocol address is ambiguous.
 628          */
 629         if (rtinfo->rti_ifp == NULL) {
 630                 struct sockaddr *ifpaddr;
 631
 632                 ifpaddr = rtinfo->rti_info[RTAX_IFP];
 633                 if (ifpaddr != NULL && ifpaddr->sa_family == AF_LINK) {
 634                         struct ifaddr *ifa;
 635
 636                         ifa = ifa_ifwithnet(ifpaddr);
 637                         if (ifa != NULL)
 638                                 rtinfo->rti_ifp = ifa->ifa_ifp;
 639                 }
 640         }
 641
 642         if (rtinfo->rti_ifa == NULL && ifaaddr != NULL)
 643                 rtinfo->rti_ifa = ifa_ifwithaddr(ifaaddr);
 644         if (rtinfo->rti_ifa == NULL) {
 645                 struct sockaddr *sa;
 646
 647                 sa = ifaaddr != NULL ? ifaaddr :
 648                     (gateway != NULL ? gateway : dst);
 649                 if (sa != NULL && rtinfo->rti_ifp != NULL)
 650                         rtinfo->rti_ifa = ifaof_ifpforaddr(sa, rtinfo->rti_ifp);
 651                 else if (dst != NULL && gateway != NULL)
 652                         rtinfo->rti_ifa = ifa_ifwithroute(flags, dst, gateway);
 653                 else if (sa != NULL)
 654                         rtinfo->rti_ifa = ifa_ifwithroute(flags, sa, sa);
 655         }
 656         if (rtinfo->rti_ifa == NULL)
 657                 return (ENETUNREACH);
 658
 659         if (rtinfo->rti_ifp == NULL)
 660                 rtinfo->rti_ifp = rtinfo->rti_ifa->ifa_ifp;
 661         return (0);
 662 }
 663
 664 /*
 665  * Do appropriate manipulations of a routing tree given
 666  * all the bits of info needed
 667  */
 668 int
 669 rtrequest(
 670         int req,
 671         struct sockaddr *dst,
 672         struct sockaddr *gateway,
 673         struct sockaddr *netmask,
 674         int flags,
 675         struct rtentry **ret_nrt)
 676 {
 677         struct rt_addrinfo rtinfo;
 678
 679         bzero(&rtinfo, sizeof(struct rt_addrinfo));
 680         rtinfo.rti_info[RTAX_DST] = dst;
 681         rtinfo.rti_info[RTAX_GATEWAY] = gateway;
 682         rtinfo.rti_info[RTAX_NETMASK] = netmask;
 683         rtinfo.rti_flags = flags;
 684         return rtrequest1(req, &rtinfo, ret_nrt);
 685 }
 686
 687 int
 688 rtrequest_global(
 689         int req,
 690         struct sockaddr *dst,
 691         struct sockaddr *gateway,
 692         struct sockaddr *netmask,
 693         int flags)
 694 {
 695         struct rt_addrinfo rtinfo;
 696
 697         bzero(&rtinfo, sizeof(struct rt_addrinfo));
 698         rtinfo.rti_info[RTAX_DST] = dst;
 699         rtinfo.rti_info[RTAX_GATEWAY] = gateway;
 700         rtinfo.rti_info[RTAX_NETMASK] = netmask;
 701         rtinfo.rti_flags = flags;
 702         return rtrequest1_global(req, &rtinfo, NULL, NULL);
 703 }
 704
 705 struct netmsg_rtq {
 706         struct netmsg_base      base;
 707         int                     req;
 708         struct rt_addrinfo      *rtinfo;
 709         rtrequest1_callback_func_t callback;
 710         void                    *arg;
 711 };
 712
 713 int
 714 rtrequest1_global(int req, struct rt_addrinfo *rtinfo,
 715                   rtrequest1_callback_func_t callback, void *arg)
 716 {
 717         int error;
 718         struct netmsg_rtq msg;
 719
 720         netmsg_init(&msg.base, NULL, &curthread->td_msgport,
 721                     0, rtrequest1_msghandler);
 722         msg.base.lmsg.ms_error = -1;
 723         msg.req = req;
 724         msg.rtinfo = rtinfo;
 725         msg.callback = callback;
 726         msg.arg = arg;
 727         error = lwkt_domsg(rtable_portfn(0), &msg.base.lmsg, 0);
 728         return (error);
 729 }
 730
 731 /*
 732  * Handle a route table request on the current cpu.  Since the route table's
 733  * are supposed to be identical on each cpu, an error occuring later in the
 734  * message chain is considered system-fatal.
 735  */
 736 static void
 737 rtrequest1_msghandler(netmsg_t msg)
 738 {
 739         struct netmsg_rtq *rmsg = (void *)msg;
 740         struct rt_addrinfo rtinfo;
 741         struct rtentry *rt = NULL;
 742         int nextcpu;
 743         int error;
 744
 745         /*
 746          * Copy the rtinfo.  We need to make sure that the original
 747          * rtinfo, which is setup by the caller, in the netmsg will
 748          * _not_ be changed; else the next CPU on the netmsg forwarding
 749          * path will see a different rtinfo than what this CPU has seen.
 750          */
 751         rtinfo = *rmsg->rtinfo;
 752
 753         error = rtrequest1(rmsg->req, &rtinfo, &rt);
 754         if (rt)
 755                 --rt->rt_refcnt;
 756         if (rmsg->callback)
 757                 rmsg->callback(rmsg->req, error, &rtinfo, rt, rmsg->arg);
 758
 759         /*
 760          * RTM_DELETE's are propogated even if an error occurs, since a
 761          * cloned route might be undergoing deletion and cloned routes
 762          * are not necessarily replicated.  An overall error is returned
 763          * only if no cpus have the route in question.
 764          */
 765         if (rmsg->base.lmsg.ms_error < 0 || error == 0)
 766                 rmsg->base.lmsg.ms_error = error;
 767
 768         nextcpu = mycpuid + 1;
 769         if (error && rmsg->req != RTM_DELETE) {
 770                 if (mycpuid != 0) {
 771                         panic("rtrequest1_msghandler: rtrequest table "
 772                               "error was cpu%d, err %d\n", mycpuid, error);
 773                 }
 774                 lwkt_replymsg(&rmsg->base.lmsg, error);
 775         } else if (nextcpu < ncpus) {
 776                 lwkt_forwardmsg(rtable_portfn(nextcpu), &rmsg->base.lmsg);
 777         } else {
 778                 lwkt_replymsg(&rmsg->base.lmsg, rmsg->base.lmsg.ms_error);
 779         }
 780 }
 781
 782 int
 783 rtrequest1(int req, struct rt_addrinfo *rtinfo, struct rtentry **ret_nrt)
 784 {
 785         struct sockaddr *dst = rtinfo->rti_info[RTAX_DST];
 786         struct rtentry *rt;
 787         struct radix_node *rn;
 788         struct radix_node_head *rnh;
 789         struct ifaddr *ifa;
 790         struct sockaddr *ndst;
 791         boolean_t reportmsg;
 792         int error = 0;
 793
 794 #define gotoerr(x) { error = x ; goto bad; }
 795
 796 #ifdef ROUTE_DEBUG
 797         if (route_debug)
 798                 rt_addrinfo_print(req, rtinfo);
 799 #endif
 800
 801         crit_enter();
 802         /*
 803          * Find the correct routing tree to use for this Address Family
 804          */
 805         if ((rnh = rt_tables[mycpuid][dst->sa_family]) == NULL)
 806                 gotoerr(EAFNOSUPPORT);
 807
 808         /*
 809          * If we are adding a host route then we don't want to put
 810          * a netmask in the tree, nor do we want to clone it.
 811          */
 812         if (rtinfo->rti_flags & RTF_HOST) {
 813                 rtinfo->rti_info[RTAX_NETMASK] = NULL;
 814                 rtinfo->rti_flags &= ~(RTF_CLONING | RTF_PRCLONING);
 815         }
 816
 817         switch (req) {
 818         case RTM_DELETE:
 819                 /* Remove the item from the tree. */
 820                 rn = rnh->rnh_deladdr((char *)rtinfo->rti_info[RTAX_DST],
 821                                       (char *)rtinfo->rti_info[RTAX_NETMASK],
 822                                       rnh);
 823                 if (rn == NULL)
 824                         gotoerr(ESRCH);
 825                 KASSERT(!(rn->rn_flags & (RNF_ACTIVE | RNF_ROOT)),
 826                         ("rnh_deladdr returned flags 0x%x", rn->rn_flags));
 827                 rt = (struct rtentry *)rn;
 828
 829                 /* ref to prevent a deletion race */
 830                 ++rt->rt_refcnt;
 831
 832                 /* Free any routes cloned from this one. */
 833                 if ((rt->rt_flags & (RTF_CLONING | RTF_PRCLONING)) &&
 834                     rt_mask(rt) != NULL) {
 835                         rnh->rnh_walktree_from(rnh, (char *)rt_key(rt),
 836                                                (char *)rt_mask(rt),
 837                                                rt_fixdelete, rt);
 838                 }
 839
 840                 if (rt->rt_gwroute != NULL) {
 841                         RTFREE(rt->rt_gwroute);
 842                         rt->rt_gwroute = NULL;
 843                 }
 844
 845                 /*
 846                  * NB: RTF_UP must be set during the search above,
 847                  * because we might delete the last ref, causing
 848                  * rt to get freed prematurely.
 849                  */
 850                 rt->rt_flags &= ~RTF_UP;
 851
 852 #ifdef ROUTE_DEBUG
 853                 if (route_debug)
 854                         rt_print(rtinfo, rt);
 855 #endif
 856
 857                 /* Give the protocol a chance to keep things in sync. */
 858                 if ((ifa = rt->rt_ifa) && ifa->ifa_rtrequest)
 859                         ifa->ifa_rtrequest(RTM_DELETE, rt, rtinfo);
 860
 861                 /*
 862                  * If the caller wants it, then it can have it,
 863                  * but it's up to it to free the rtentry as we won't be
 864                  * doing it.
 865                  */
 866                 KASSERT(rt->rt_refcnt >= 0,
 867                         ("rtrequest1(DELETE): refcnt %ld", rt->rt_refcnt));
 868                 if (ret_nrt != NULL) {
 869                         /* leave ref intact for return */
 870                         *ret_nrt = rt;
 871                 } else {
 872                         /* deref / attempt to destroy */
 873                         rtfree(rt);
 874                 }
 875                 break;
 876
 877         case RTM_RESOLVE:
 878                 if (ret_nrt == NULL || (rt = *ret_nrt) == NULL)
 879                         gotoerr(EINVAL);
 880                 ifa = rt->rt_ifa;
 881                 rtinfo->rti_flags =
 882                     rt->rt_flags & ~(RTF_CLONING | RTF_PRCLONING | RTF_STATIC);
 883                 rtinfo->rti_flags |= RTF_WASCLONED;
 884                 rtinfo->rti_info[RTAX_GATEWAY] = rt->rt_gateway;
 885                 if ((rtinfo->rti_info[RTAX_NETMASK] = rt->rt_genmask) == NULL)
 886                         rtinfo->rti_flags |= RTF_HOST;
 887                 rtinfo->rti_info[RTAX_MPLS1] = rt->rt_shim[0];
 888                 rtinfo->rti_info[RTAX_MPLS2] = rt->rt_shim[1];
 889                 rtinfo->rti_info[RTAX_MPLS3] = rt->rt_shim[2];
 890                 goto makeroute;
 891
 892         case RTM_ADD:
 893                 KASSERT(!(rtinfo->rti_flags & RTF_GATEWAY) ||
 894                         rtinfo->rti_info[RTAX_GATEWAY] != NULL,
 895                     ("rtrequest: GATEWAY but no gateway"));
 896
 897                 if (rtinfo->rti_ifa == NULL && (error = rt_getifa(rtinfo)))
 898                         gotoerr(error);
 899                 ifa = rtinfo->rti_ifa;
 900 makeroute:
 901                 R_Malloc(rt, struct rtentry *, sizeof(struct rtentry));
 902                 if (rt == NULL) {
 903                         if (req == RTM_ADD) {
 904                                 kprintf("rtrequest1: alloc rtentry failed on "
 905                                     "cpu%d\n", mycpuid);
 906                         }
 907                         gotoerr(ENOBUFS);
 908                 }
 909                 bzero(rt, sizeof(struct rtentry));
 910                 rt->rt_flags = RTF_UP | rtinfo->rti_flags;
 911                 rt->rt_cpuid = mycpuid;
 912
 913                 if (mycpuid != 0 && req == RTM_ADD) {
 914                         /* For RTM_ADD, we have already sent rtmsg on CPU0. */
 915                         reportmsg = RTL_DONTREPORT;
 916                 } else {
 917                         /*
 918                          * For RTM_ADD, we only send rtmsg on CPU0.
 919                          * For RTM_RESOLVE, we always send rtmsg. XXX
 920                          */
 921                         reportmsg = RTL_REPORTMSG;
 922                 }
 923                 error = rt_setgate(rt, dst, rtinfo->rti_info[RTAX_GATEWAY],
 924                                    reportmsg);
 925                 if (error != 0) {
 926                         Free(rt);
 927                         gotoerr(error);
 928                 }
 929
 930                 ndst = rt_key(rt);
 931                 if (rtinfo->rti_info[RTAX_NETMASK] != NULL)
 932                         rt_maskedcopy(dst, ndst,
 933                                       rtinfo->rti_info[RTAX_NETMASK]);
 934                 else
 935                         bcopy(dst, ndst, dst->sa_len);
 936
 937                 if (rtinfo->rti_info[RTAX_MPLS1] != NULL)
 938                         rt_setshims(rt, rtinfo->rti_info);
 939
 940                 /*
 941                  * Note that we now have a reference to the ifa.
 942                  * This moved from below so that rnh->rnh_addaddr() can
 943                  * examine the ifa and  ifa->ifa_ifp if it so desires.
 944                  */
 945                 IFAREF(ifa);
 946                 rt->rt_ifa = ifa;
 947                 rt->rt_ifp = ifa->ifa_ifp;
 948                 /* XXX mtu manipulation will be done in rnh_addaddr -- itojun */
 949
 950                 rn = rnh->rnh_addaddr((char *)ndst,
 951                                       (char *)rtinfo->rti_info[RTAX_NETMASK],
 952                                       rnh, rt->rt_nodes);
 953                 if (rn == NULL) {
 954                         struct rtentry *oldrt;
 955
 956                         /*
 957                          * We already have one of these in the tree.
 958                          * We do a special hack: if the old route was
 959                          * cloned, then we blow it away and try
 960                          * re-inserting the new one.
 961                          */
 962                         oldrt = rtpurelookup(ndst);
 963                         if (oldrt != NULL) {
 964                                 --oldrt->rt_refcnt;
 965                                 if (oldrt->rt_flags & RTF_WASCLONED) {
 966                                         rtrequest(RTM_DELETE, rt_key(oldrt),
 967                                                   oldrt->rt_gateway,
 968                                                   rt_mask(oldrt),
 969                                                   oldrt->rt_flags, NULL);
 970                                         rn = rnh->rnh_addaddr((char *)ndst,
 971                                             (char *)
 972                                                 rtinfo->rti_info[RTAX_NETMASK],
 973                                             rnh, rt->rt_nodes);
 974                                 }
 975                         }
 976                 }
 977
 978                 /*
 979                  * If it still failed to go into the tree,
 980                  * then un-make it (this should be a function).
 981                  */
 982                 if (rn == NULL) {
 983                         if (rt->rt_gwroute != NULL)
 984                                 rtfree(rt->rt_gwroute);
 985                         IFAFREE(ifa);
 986                         Free(rt_key(rt));
 987                         Free(rt);
 988                         gotoerr(EEXIST);
 989                 }
 990
 991                 /*
 992                  * If we got here from RESOLVE, then we are cloning
 993                  * so clone the rest, and note that we
 994                  * are a clone (and increment the parent's references)
 995                  */
 996                 if (req == RTM_RESOLVE) {
 997                         rt->rt_rmx = (*ret_nrt)->rt_rmx;    /* copy metrics */
 998                         rt->rt_rmx.rmx_pksent = 0;  /* reset packet counter */
 999                         if ((*ret_nrt)->rt_flags &
1000                                        (RTF_CLONING | RTF_PRCLONING)) {
1001                                 rt->rt_parent = *ret_nrt;
1002                                 (*ret_nrt)->rt_refcnt++;
1003                         }
1004                 }
1005
1006                 /*
1007                  * if this protocol has something to add to this then
1008                  * allow it to do that as well.
1009                  */
1010                 if (ifa->ifa_rtrequest != NULL)
1011                         ifa->ifa_rtrequest(req, rt, rtinfo);
1012
1013                 /*
1014                  * We repeat the same procedure from rt_setgate() here because
1015                  * it doesn't fire when we call it there because the node
1016                  * hasn't been added to the tree yet.
1017                  */
1018                 if (req == RTM_ADD && !(rt->rt_flags & RTF_HOST) &&
1019                     rt_mask(rt) != NULL) {
1020                         struct rtfc_arg arg = { rt, rnh };
1021
1022                         rnh->rnh_walktree_from(rnh, (char *)rt_key(rt),
1023                                                (char *)rt_mask(rt),
1024                                                rt_fixchange, &arg);
1025                 }
1026
1027 #ifdef ROUTE_DEBUG
1028                 if (route_debug)
1029                         rt_print(rtinfo, rt);
1030 #endif
1031                 /*
1032                  * Return the resulting rtentry,
1033                  * increasing the number of references by one.
1034                  */
1035                 if (ret_nrt != NULL) {
1036                         rt->rt_refcnt++;
1037                         *ret_nrt = rt;
1038                 }
1039                 break;
1040         default:
1041                 error = EOPNOTSUPP;
1042         }
1043 bad:
1044 #ifdef ROUTE_DEBUG
1045         if (route_debug) {
1046                 if (error)
1047                         kprintf("rti %p failed error %d\n", rtinfo, error);
1048                 else
1049                         kprintf("rti %p succeeded\n", rtinfo);
1050         }
1051 #endif
1052         crit_exit();
1053         return (error);
1054 }
1055
1056 /*
1057  * Called from rtrequest(RTM_DELETE, ...) to fix up the route's ``family''
1058  * (i.e., the routes related to it by the operation of cloning).  This
1059  * routine is iterated over all potential former-child-routes by way of
1060  * rnh->rnh_walktree_from() above, and those that actually are children of
1061  * the late parent (passed in as VP here) are themselves deleted.
1062  */
1063 static int
1064 rt_fixdelete(struct radix_node *rn, void *vp)
1065 {
1066         struct rtentry *rt = (struct rtentry *)rn;
1067         struct rtentry *rt0 = vp;
1068
1069         if (rt->rt_parent == rt0 &&
1070             !(rt->rt_flags & (RTF_PINNED | RTF_CLONING | RTF_PRCLONING))) {
1071                 return rtrequest(RTM_DELETE, rt_key(rt), NULL, rt_mask(rt),
1072                                  rt->rt_flags, NULL);
1073         }
1074         return 0;
1075 }
1076
1077 /*
1078  * This routine is called from rt_setgate() to do the analogous thing for
1079  * adds and changes.  There is the added complication in this case of a
1080  * middle insert; i.e., insertion of a new network route between an older
1081  * network route and (cloned) host routes.  For this reason, a simple check
1082  * of rt->rt_parent is insufficient; each candidate route must be tested
1083  * against the (mask, value) of the new route (passed as before in vp)
1084  * to see if the new route matches it.
1085  *
1086  * XXX - it may be possible to do fixdelete() for changes and reserve this
1087  * routine just for adds.  I'm not sure why I thought it was necessary to do
1088  * changes this way.
1089  */
1090 #ifdef DEBUG
1091 static int rtfcdebug = 0;
1092 #endif
1093
1094 static int
1095 rt_fixchange(struct radix_node *rn, void *vp)
1096 {
1097         struct rtentry *rt = (struct rtentry *)rn;
1098         struct rtfc_arg *ap = vp;
1099         struct rtentry *rt0 = ap->rt0;
1100         struct radix_node_head *rnh = ap->rnh;
1101         u_char *xk1, *xm1, *xk2, *xmp;
1102         int i, len, mlen;
1103
1104 #ifdef DEBUG
1105         if (rtfcdebug)
1106                 kprintf("rt_fixchange: rt %p, rt0 %p\n", rt, rt0);
1107 #endif
1108
1109         if (rt->rt_parent == NULL ||
1110             (rt->rt_flags & (RTF_PINNED | RTF_CLONING | RTF_PRCLONING))) {
1111 #ifdef DEBUG
1112                 if (rtfcdebug) kprintf("no parent, pinned or cloning\n");
1113 #endif
1114                 return 0;
1115         }
1116
1117         if (rt->rt_parent == rt0) {
1118 #ifdef DEBUG
1119                 if (rtfcdebug) kprintf("parent match\n");
1120 #endif
1121                 return rtrequest(RTM_DELETE, rt_key(rt), NULL, rt_mask(rt),
1122                                  rt->rt_flags, NULL);
1123         }
1124
1125         /*
1126          * There probably is a function somewhere which does this...
1127          * if not, there should be.
1128          */
1129         len = imin(rt_key(rt0)->sa_len, rt_key(rt)->sa_len);
1130
1131         xk1 = (u_char *)rt_key(rt0);
1132         xm1 = (u_char *)rt_mask(rt0);
1133         xk2 = (u_char *)rt_key(rt);
1134
1135         /* avoid applying a less specific route */
1136         xmp = (u_char *)rt_mask(rt->rt_parent);
1137         mlen = rt_key(rt->rt_parent)->sa_len;
1138         if (mlen > rt_key(rt0)->sa_len) {
1139 #ifdef DEBUG
1140                 if (rtfcdebug)
1141                         kprintf("rt_fixchange: inserting a less "
1142                                "specific route\n");
1143 #endif
1144                 return 0;
1145         }
1146         for (i = rnh->rnh_treetop->rn_offset; i < mlen; i++) {
1147                 if ((xmp[i] & ~(xmp[i] ^ xm1[i])) != xmp[i]) {
1148 #ifdef DEBUG
1149                         if (rtfcdebug)
1150                                 kprintf("rt_fixchange: inserting a less "
1151                                        "specific route\n");
1152 #endif
1153                         return 0;
1154                 }
1155         }
1156
1157         for (i = rnh->rnh_treetop->rn_offset; i < len; i++) {
1158                 if ((xk2[i] & xm1[i]) != xk1[i]) {
1159 #ifdef DEBUG
1160                         if (rtfcdebug) kprintf("no match\n");
1161 #endif
1162                         return 0;
1163                 }
1164         }
1165
1166         /*
1167          * OK, this node is a clone, and matches the node currently being
1168          * changed/added under the node's mask.  So, get rid of it.
1169          */
1170 #ifdef DEBUG
1171         if (rtfcdebug) kprintf("deleting\n");
1172 #endif
1173         return rtrequest(RTM_DELETE, rt_key(rt), NULL, rt_mask(rt),
1174                          rt->rt_flags, NULL);
1175 }
1176
1177 #define ROUNDUP(a) (a>0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long))
1178
1179 int
1180 rt_setgate(struct rtentry *rt0, struct sockaddr *dst, struct sockaddr *gate,
1181            boolean_t generate_report)
1182 {
1183         char *space, *oldspace;
1184         int dlen = ROUNDUP(dst->sa_len), glen = ROUNDUP(gate->sa_len);
1185         struct rtentry *rt = rt0;
1186         struct radix_node_head *rnh = rt_tables[mycpuid][dst->sa_family];
1187
1188         /*
1189          * A host route with the destination equal to the gateway
1190          * will interfere with keeping LLINFO in the routing
1191          * table, so disallow it.
1192          */
1193         if (((rt0->rt_flags & (RTF_HOST | RTF_GATEWAY | RTF_LLINFO)) ==
1194                               (RTF_HOST | RTF_GATEWAY)) &&
1195             dst->sa_len == gate->sa_len &&
1196             sa_equal(dst, gate)) {
1197                 /*
1198                  * The route might already exist if this is an RTM_CHANGE
1199                  * or a routing redirect, so try to delete it.
1200                  */
1201                 if (rt_key(rt0) != NULL)
1202                         rtrequest(RTM_DELETE, rt_key(rt0), rt0->rt_gateway,
1203                                   rt_mask(rt0), rt0->rt_flags, NULL);
1204                 return EADDRNOTAVAIL;
1205         }
1206
1207         /*
1208          * Both dst and gateway are stored in the same malloc'ed chunk
1209          * (If I ever get my hands on....)
1210          * if we need to malloc a new chunk, then keep the old one around
1211          * till we don't need it any more.
1212          */
1213         if (rt->rt_gateway == NULL || glen > ROUNDUP(rt->rt_gateway->sa_len)) {
1214                 oldspace = (char *)rt_key(rt);
1215                 R_Malloc(space, char *, dlen + glen);
1216                 if (space == NULL)
1217                         return ENOBUFS;
1218                 rt->rt_nodes->rn_key = space;
1219         } else {
1220                 space = (char *)rt_key(rt);     /* Just use the old space. */
1221                 oldspace = NULL;
1222         }
1223
1224         /* Set the gateway value. */
1225         rt->rt_gateway = (struct sockaddr *)(space + dlen);
1226         bcopy(gate, rt->rt_gateway, glen);
1227
1228         if (oldspace != NULL) {
1229                 /*
1230                  * If we allocated a new chunk, preserve the original dst.
1231                  * This way, rt_setgate() really just sets the gate
1232                  * and leaves the dst field alone.
1233                  */
1234                 bcopy(dst, space, dlen);
1235                 Free(oldspace);
1236         }
1237
1238         /*
1239          * If there is already a gwroute, it's now almost definitely wrong
1240          * so drop it.
1241          */
1242         if (rt->rt_gwroute != NULL) {
1243                 RTFREE(rt->rt_gwroute);
1244                 rt->rt_gwroute = NULL;
1245         }
1246         if (rt->rt_flags & RTF_GATEWAY) {
1247                 /*
1248                  * Cloning loop avoidance: In the presence of
1249                  * protocol-cloning and bad configuration, it is
1250                  * possible to get stuck in bottomless mutual recursion
1251                  * (rtrequest rt_setgate rtlookup).  We avoid this
1252                  * by not allowing protocol-cloning to operate for
1253                  * gateways (which is probably the correct choice
1254                  * anyway), and avoid the resulting reference loops
1255                  * by disallowing any route to run through itself as
1256                  * a gateway.  This is obviously mandatory when we
1257                  * get rt->rt_output().
1258                  *
1259                  * This breaks TTCP for hosts outside the gateway!  XXX JH
1260                  */
1261                 rt->rt_gwroute = _rtlookup(gate, generate_report,
1262                                            RTF_PRCLONING);
1263                 if (rt->rt_gwroute == rt) {
1264                         rt->rt_gwroute = NULL;
1265                         --rt->rt_refcnt;
1266                         return EDQUOT; /* failure */
1267                 }
1268         }
1269
1270         /*
1271          * This isn't going to do anything useful for host routes, so
1272          * don't bother.  Also make sure we have a reasonable mask
1273          * (we don't yet have one during adds).
1274          */
1275         if (!(rt->rt_flags & RTF_HOST) && rt_mask(rt) != NULL) {
1276                 struct rtfc_arg arg = { rt, rnh };
1277
1278                 rnh->rnh_walktree_from(rnh, (char *)rt_key(rt),
1279                                        (char *)rt_mask(rt),
1280                                        rt_fixchange, &arg);
1281         }
1282
1283         return 0;
1284 }
1285
1286 static void
1287 rt_maskedcopy(
1288         struct sockaddr *src,
1289         struct sockaddr *dst,
1290         struct sockaddr *netmask)
1291 {
1292         u_char *cp1 = (u_char *)src;
1293         u_char *cp2 = (u_char *)dst;
1294         u_char *cp3 = (u_char *)netmask;
1295         u_char *cplim = cp2 + *cp3;
1296         u_char *cplim2 = cp2 + *cp1;
1297
1298         *cp2++ = *cp1++; *cp2++ = *cp1++; /* copies sa_len & sa_family */
1299         cp3 += 2;
1300         if (cplim > cplim2)
1301                 cplim = cplim2;
1302         while (cp2 < cplim)
1303                 *cp2++ = *cp1++ & *cp3++;
1304         if (cp2 < cplim2)
1305                 bzero(cp2, cplim2 - cp2);
1306 }
1307
1308 int
1309 rt_llroute(struct sockaddr *dst, struct rtentry *rt0, struct rtentry **drt)
1310 {
1311         struct rtentry *up_rt, *rt;
1312
1313         if (!(rt0->rt_flags & RTF_UP)) {
1314                 up_rt = rtlookup(dst);
1315                 if (up_rt == NULL)
1316                         return (EHOSTUNREACH);
1317                 up_rt->rt_refcnt--;
1318         } else
1319                 up_rt = rt0;
1320         if (up_rt->rt_flags & RTF_GATEWAY) {
1321                 if (up_rt->rt_gwroute == NULL) {
1322                         up_rt->rt_gwroute = rtlookup(up_rt->rt_gateway);
1323                         if (up_rt->rt_gwroute == NULL)
1324                                 return (EHOSTUNREACH);
1325                 } else if (!(up_rt->rt_gwroute->rt_flags & RTF_UP)) {
1326                         rtfree(up_rt->rt_gwroute);
1327                         up_rt->rt_gwroute = rtlookup(up_rt->rt_gateway);
1328                         if (up_rt->rt_gwroute == NULL)
1329                                 return (EHOSTUNREACH);
1330                 }
1331                 rt = up_rt->rt_gwroute;
1332         } else
1333                 rt = up_rt;
1334         if (rt->rt_flags & RTF_REJECT &&
1335             (rt->rt_rmx.rmx_expire == 0 ||              /* rt doesn't expire */
1336              time_second < rt->rt_rmx.rmx_expire))      /* rt not expired */
1337                 return (rt->rt_flags & RTF_HOST ?  EHOSTDOWN : EHOSTUNREACH);
1338         *drt = rt;
1339         return 0;
1340 }
1341
1342 static int
1343 rt_setshims(struct rtentry *rt, struct sockaddr **rt_shim){
1344         int i;
1345
1346         for (i=0; i<3; i++) {
1347                 struct sockaddr *shim = rt_shim[RTAX_MPLS1 + i];
1348                 int shimlen;
1349
1350                 if (shim == NULL)
1351                         break;
1352
1353                 shimlen = ROUNDUP(shim->sa_len);
1354                 R_Malloc(rt->rt_shim[i], struct sockaddr *, shimlen);
1355                 bcopy(shim, rt->rt_shim[i], shimlen);
1356         }
1357
1358         return 0;
1359 }
1360
1361 #ifdef ROUTE_DEBUG
1362
1363 /*
1364  * Print out a route table entry
1365  */
1366 void
1367 rt_print(struct rt_addrinfo *rtinfo, struct rtentry *rn)
1368 {
1369         kprintf("rti %p cpu %d route %p flags %08lx: ",
1370                 rtinfo, mycpuid, rn, rn->rt_flags);
1371         sockaddr_print(rt_key(rn));
1372         kprintf(" mask ");
1373         sockaddr_print(rt_mask(rn));
1374         kprintf(" gw ");
1375         sockaddr_print(rn->rt_gateway);
1376         kprintf(" ifc \"%s\"", rn->rt_ifp ? rn->rt_ifp->if_dname : "?");
1377         kprintf(" ifa %p\n", rn->rt_ifa);
1378 }
1379
1380 void
1381 rt_addrinfo_print(int cmd, struct rt_addrinfo *rti)
1382 {
1383         int didit = 0;
1384         int i;
1385
1386 #ifdef ROUTE_DEBUG
1387         if (cmd == RTM_DELETE && route_debug > 1)
1388                 print_backtrace(-1);
1389 #endif
1390
1391         switch(cmd) {
1392         case RTM_ADD:
1393                 kprintf("ADD ");
1394                 break;
1395         case RTM_RESOLVE:
1396                 kprintf("RES ");
1397                 break;
1398         case RTM_DELETE:
1399                 kprintf("DEL ");
1400                 break;
1401         default:
1402                 kprintf("C%02d ", cmd);
1403                 break;
1404         }
1405         kprintf("rti %p cpu %d ", rti, mycpuid);
1406         for (i = 0; i < rti->rti_addrs; ++i) {
1407                 if (rti->rti_info[i] == NULL)
1408                         continue;
1409                 if (didit)
1410                         kprintf(" ,");
1411                 switch(i) {
1412                 case RTAX_DST:
1413                         kprintf("(DST ");
1414                         break;
1415                 case RTAX_GATEWAY:
1416                         kprintf("(GWY ");
1417                         break;
1418                 case RTAX_NETMASK:
1419                         kprintf("(MSK ");
1420                         break;
1421                 case RTAX_GENMASK:
1422                         kprintf("(GEN ");
1423                         break;
1424                 case RTAX_IFP:
1425                         kprintf("(IFP ");
1426                         break;
1427                 case RTAX_IFA:
1428                         kprintf("(IFA ");
1429                         break;
1430                 case RTAX_AUTHOR:
1431                         kprintf("(AUT ");
1432                         break;
1433                 case RTAX_BRD:
1434                         kprintf("(BRD ");
1435                         break;
1436                 default:
1437                         kprintf("(?%02d ", i);
1438                         break;
1439                 }
1440                 sockaddr_print(rti->rti_info[i]);
1441                 kprintf(")");
1442                 didit = 1;
1443         }
1444         kprintf("\n");
1445 }
1446
1447 void
1448 sockaddr_print(struct sockaddr *sa)
1449 {
1450         struct sockaddr_in *sa4;
1451         struct sockaddr_in6 *sa6;
1452         int len;
1453         int i;
1454
1455         if (sa == NULL) {
1456                 kprintf("NULL");
1457                 return;
1458         }
1459
1460         len = sa->sa_len - offsetof(struct sockaddr, sa_data[0]);
1461
1462         switch(sa->sa_family) {
1463         case AF_INET:
1464         case AF_INET6:
1465         default:
1466                 switch(sa->sa_family) {
1467                 case AF_INET:
1468                         sa4 = (struct sockaddr_in *)sa;
1469                         kprintf("INET %d %d.%d.%d.%d",
1470                                 ntohs(sa4->sin_port),
1471                                 (ntohl(sa4->sin_addr.s_addr) >> 24) & 255,
1472                                 (ntohl(sa4->sin_addr.s_addr) >> 16) & 255,
1473                                 (ntohl(sa4->sin_addr.s_addr) >> 8) & 255,
1474                                 (ntohl(sa4->sin_addr.s_addr) >> 0) & 255
1475                         );
1476                         break;
1477                 case AF_INET6:
1478                         sa6 = (struct sockaddr_in6 *)sa;
1479                         kprintf("INET6 %d %04x:%04x%04x:%04x:%04x:%04x:%04x:%04x",
1480                                 ntohs(sa6->sin6_port),
1481                                 sa6->sin6_addr.s6_addr16[0],
1482                                 sa6->sin6_addr.s6_addr16[1],
1483                                 sa6->sin6_addr.s6_addr16[2],
1484                                 sa6->sin6_addr.s6_addr16[3],
1485                                 sa6->sin6_addr.s6_addr16[4],
1486                                 sa6->sin6_addr.s6_addr16[5],
1487                                 sa6->sin6_addr.s6_addr16[6],
1488                                 sa6->sin6_addr.s6_addr16[7]
1489                         );
1490                         break;
1491                 default:
1492                         kprintf("AF%d ", sa->sa_family);
1493                         while (len > 0 && sa->sa_data[len-1] == 0)
1494                                 --len;
1495
1496                         for (i = 0; i < len; ++i) {
1497                                 if (i)
1498                                         kprintf(".");
1499                                 kprintf("%d", (unsigned char)sa->sa_data[i]);
1500                         }
1501                         break;
1502                 }
1503         }
1504 }
1505
1506 #endif
1507
1508 /*
1509  * Set up a routing table entry, normally for an interface.
1510  */
1511 int
1512 rtinit(struct ifaddr *ifa, int cmd, int flags)
1513 {
1514         struct sockaddr *dst, *deldst, *netmask;
1515         struct mbuf *m = NULL;
1516         struct radix_node_head *rnh;
1517         struct radix_node *rn;
1518         struct rt_addrinfo rtinfo;
1519         int error;
1520
1521         if (flags & RTF_HOST) {
1522                 dst = ifa->ifa_dstaddr;
1523                 netmask = NULL;
1524         } else {
1525                 dst = ifa->ifa_addr;
1526                 netmask = ifa->ifa_netmask;
1527         }
1528         /*
1529          * If it's a delete, check that if it exists, it's on the correct
1530          * interface or we might scrub a route to another ifa which would
1531          * be confusing at best and possibly worse.
1532          */
1533         if (cmd == RTM_DELETE) {
1534                 /*
1535                  * It's a delete, so it should already exist..
1536                  * If it's a net, mask off the host bits
1537                  * (Assuming we have a mask)
1538                  */
1539                 if (netmask != NULL) {
1540                         m = m_get(MB_DONTWAIT, MT_SONAME);
1541                         if (m == NULL)
1542                                 return (ENOBUFS);
1543                         mbuftrackid(m, 34);
1544                         deldst = mtod(m, struct sockaddr *);
1545                         rt_maskedcopy(dst, deldst, netmask);
1546                         dst = deldst;
1547                 }
1548                 /*
1549                  * Look up an rtentry that is in the routing tree and
1550                  * contains the correct info.
1551                  */
1552                 if ((rnh = rt_tables[mycpuid][dst->sa_family]) == NULL ||
1553                     (rn = rnh->rnh_lookup((char *)dst,
1554                                           (char *)netmask, rnh)) == NULL ||
1555                     ((struct rtentry *)rn)->rt_ifa != ifa ||
1556                     !sa_equal((struct sockaddr *)rn->rn_key, dst)) {
1557                         if (m != NULL)
1558                                 m_free(m);
1559                         return (flags & RTF_HOST ? EHOSTUNREACH : ENETUNREACH);
1560                 }
1561                 /* XXX */
1562 #if 0
1563                 else {
1564                         /*
1565                          * One would think that as we are deleting, and we know
1566                          * it doesn't exist, we could just return at this point
1567                          * with an "ELSE" clause, but apparently not..
1568                          */
1569                         return (flags & RTF_HOST ? EHOSTUNREACH : ENETUNREACH);
1570                 }
1571 #endif
1572         }
1573         /*
1574          * Do the actual request
1575          */
1576         bzero(&rtinfo, sizeof(struct rt_addrinfo));
1577         rtinfo.rti_info[RTAX_DST] = dst;
1578         rtinfo.rti_info[RTAX_GATEWAY] = ifa->ifa_addr;
1579         rtinfo.rti_info[RTAX_NETMASK] = netmask;
1580         rtinfo.rti_flags = flags | ifa->ifa_flags;
1581         rtinfo.rti_ifa = ifa;
1582         error = rtrequest1_global(cmd, &rtinfo, rtinit_rtrequest_callback, ifa);
1583         if (m != NULL)
1584                 m_free(m);
1585         return (error);
1586 }
1587
1588 static void
1589 rtinit_rtrequest_callback(int cmd, int error,
1590                           struct rt_addrinfo *rtinfo, struct rtentry *rt,
1591                           void *arg)
1592 {
1593         struct ifaddr *ifa = arg;
1594
1595         if (error == 0 && rt) {
1596                 if (mycpuid == 0) {
1597                         ++rt->rt_refcnt;
1598                         rt_newaddrmsg(cmd, ifa, error, rt);
1599                         --rt->rt_refcnt;
1600                 }
1601                 if (cmd == RTM_DELETE) {
1602                         if (rt->rt_refcnt == 0) {
1603                                 ++rt->rt_refcnt;
1604                                 rtfree(rt);
1605                         }
1606                 }
1607         }
1608 }
1609
1610 struct netmsg_rts {
1611         struct netmsg_base      base;
1612         int                     req;
1613         struct rt_addrinfo      *rtinfo;
1614         rtsearch_callback_func_t callback;
1615         void                    *arg;
1616         boolean_t               exact_match;
1617         int                     found_cnt;
1618 };
1619
1620 int
1621 rtsearch_global(int req, struct rt_addrinfo *rtinfo,
1622                 rtsearch_callback_func_t callback, void *arg,
1623                 boolean_t exact_match)
1624 {
1625         struct netmsg_rts msg;
1626
1627         netmsg_init(&msg.base, NULL, &curthread->td_msgport,
1628                     0, rtsearch_msghandler);
1629         msg.req = req;
1630         msg.rtinfo = rtinfo;
1631         msg.callback = callback;
1632         msg.arg = arg;
1633         msg.exact_match = exact_match;
1634         msg.found_cnt = 0;
1635         return lwkt_domsg(rtable_portfn(0), &msg.base.lmsg, 0);
1636 }
1637
1638 static void
1639 rtsearch_msghandler(netmsg_t msg)
1640 {
1641         struct netmsg_rts *rmsg = (void *)msg;
1642         struct rt_addrinfo rtinfo;
1643         struct radix_node_head *rnh;
1644         struct rtentry *rt;
1645         int nextcpu, error;
1646
1647         /*
1648          * Copy the rtinfo.  We need to make sure that the original
1649          * rtinfo, which is setup by the caller, in the netmsg will
1650          * _not_ be changed; else the next CPU on the netmsg forwarding
1651          * path will see a different rtinfo than what this CPU has seen.
1652          */
1653         rtinfo = *rmsg->rtinfo;
1654
1655         /*
1656          * Find the correct routing tree to use for this Address Family
1657          */
1658         if ((rnh = rt_tables[mycpuid][rtinfo.rti_dst->sa_family]) == NULL) {
1659                 if (mycpuid != 0)
1660                         panic("partially initialized routing tables");
1661                 lwkt_replymsg(&rmsg->base.lmsg, EAFNOSUPPORT);
1662                 return;
1663         }
1664
1665         /*
1666          * Correct rtinfo for the host route searching.
1667          */
1668         if (rtinfo.rti_flags & RTF_HOST) {
1669                 rtinfo.rti_netmask = NULL;
1670                 rtinfo.rti_flags &= ~(RTF_CLONING | RTF_PRCLONING);
1671         }
1672
1673         rt = (struct rtentry *)
1674              rnh->rnh_lookup((char *)rtinfo.rti_dst,
1675                              (char *)rtinfo.rti_netmask, rnh);
1676
1677         /*
1678          * If we are asked to do the "exact match", we need to make sure
1679          * that host route searching got a host route while a network
1680          * route searching got a network route.
1681          */
1682         if (rt != NULL && rmsg->exact_match &&
1683             ((rt->rt_flags ^ rtinfo.rti_flags) & RTF_HOST))
1684                 rt = NULL;
1685
1686         if (rt == NULL) {
1687                 /*
1688                  * No matching routes have been found, don't count this
1689                  * as a critical error (here, we set 'error' to 0), just
1690                  * keep moving on, since at least prcloned routes are not
1691                  * duplicated onto each CPU.
1692                  */
1693                 error = 0;
1694         } else {
1695                 rmsg->found_cnt++;
1696
1697                 rt->rt_refcnt++;
1698                 error = rmsg->callback(rmsg->req, &rtinfo, rt, rmsg->arg,
1699                                       rmsg->found_cnt);
1700                 rt->rt_refcnt--;
1701
1702                 if (error == EJUSTRETURN) {
1703                         lwkt_replymsg(&rmsg->base.lmsg, 0);
1704                         return;
1705                 }
1706         }
1707
1708         nextcpu = mycpuid + 1;
1709         if (error) {
1710                 KKASSERT(rmsg->found_cnt > 0);
1711
1712                 /*
1713                  * Under following cases, unrecoverable error has
1714                  * not occured:
1715                  * o  Request is RTM_GET
1716                  * o  The first time that we find the route, but the
1717                  *    modification fails.
1718                  */
1719                 if (rmsg->req != RTM_GET && rmsg->found_cnt > 1) {
1720                         panic("rtsearch_msghandler: unrecoverable error "
1721                               "cpu %d", mycpuid);
1722                 }
1723                 lwkt_replymsg(&rmsg->base.lmsg, error);
1724         } else if (nextcpu < ncpus) {
1725                 lwkt_forwardmsg(rtable_portfn(nextcpu), &rmsg->base.lmsg);
1726         } else {
1727                 if (rmsg->found_cnt == 0) {
1728                         /* The requested route was never seen ... */
1729                         error = ESRCH;
1730                 }
1731                 lwkt_replymsg(&rmsg->base.lmsg, error);
1732         }
1733 }
1734
1735 int
1736 rtmask_add_global(struct sockaddr *mask)
1737 {
1738         struct netmsg_base msg;
1739
1740         netmsg_init(&msg, NULL, &curthread->td_msgport,
1741                     0, rtmask_add_msghandler);
1742         msg.lmsg.u.ms_resultp = mask;
1743
1744         return lwkt_domsg(rtable_portfn(0), &msg.lmsg, 0);
1745 }
1746
1747 struct sockaddr *
1748 _rtmask_lookup(struct sockaddr *mask, boolean_t search)
1749 {
1750         struct radix_node *n;
1751
1752 #define clen(s) (*(u_char *)(s))
1753         n = rn_addmask((char *)mask, search, 1, rn_cpumaskhead(mycpuid));
1754         if (n != NULL &&
1755             mask->sa_len >= clen(n->rn_key) &&
1756             bcmp((char *)mask + 1,
1757                  (char *)n->rn_key + 1, clen(n->rn_key) - 1) == 0) {
1758                 return (struct sockaddr *)n->rn_key;
1759         } else {
1760                 return NULL;
1761         }
1762 #undef clen
1763 }
1764
1765 static void
1766 rtmask_add_msghandler(netmsg_t msg)
1767 {
1768         struct lwkt_msg *lmsg = &msg->lmsg;
1769         struct sockaddr *mask = lmsg->u.ms_resultp;
1770         int error = 0, nextcpu;
1771
1772         if (rtmask_lookup(mask) == NULL)
1773                 error = ENOBUFS;
1774
1775         nextcpu = mycpuid + 1;
1776         if (!error && nextcpu < ncpus)
1777                 lwkt_forwardmsg(rtable_portfn(nextcpu), lmsg);
1778         else
1779                 lwkt_replymsg(lmsg, error);
1780 }
1781
1782 /* This must be before ip6_init2(), which is now SI_ORDER_MIDDLE */
1783 SYSINIT(route, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, route_init, 0);