sys/net/route.c

   1 /*
   2  * Copyright (c) 1980, 1986, 1991, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. All advertising materials mentioning features or use of this software
  14  *    must display the following acknowledgement:
  15  *      This product includes software developed by the University of
  16  *      California, Berkeley and its contributors.
  17  * 4. Neither the name of the University nor the names of its contributors
  18  *    may be used to endorse or promote products derived from this software
  19  *    without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31  * SUCH DAMAGE.
  32  *
  33  *      @(#)route.c     8.3 (Berkeley) 1/9/95
  34  * $FreeBSD: src/sys/net/route.c,v 1.59.2.10 2003/01/17 08:04:00 ru Exp $
  35  * $DragonFly: src/sys/net/route.c,v 1.2 2003/06/17 04:28:48 dillon Exp $
  36  */
  37
  38 #include "opt_inet.h"
  39
  40 #include <sys/param.h>
  41 #include <sys/systm.h>
  42 #include <sys/malloc.h>
  43 #include <sys/mbuf.h>
  44 #include <sys/socket.h>
  45 #include <sys/domain.h>
  46 #include <sys/kernel.h>
  47
  48 #include <net/if.h>
  49 #include <net/route.h>
  50
  51 #include <netinet/in.h>
  52 #include <netinet/ip_mroute.h>
  53
  54 #define SA(p) ((struct sockaddr *)(p))
  55
  56 struct route_cb route_cb;
  57 static struct rtstat rtstat;
  58 struct radix_node_head *rt_tables[AF_MAX+1];
  59
  60 static int      rttrash;                /* routes not in table but not freed */
  61
  62 static void rt_maskedcopy __P((struct sockaddr *,
  63             struct sockaddr *, struct sockaddr *));
  64 static void rtable_init __P((void **));
  65
  66 static void
  67 rtable_init(table)
  68         void **table;
  69 {
  70         struct domain *dom;
  71         for (dom = domains; dom; dom = dom->dom_next)
  72                 if (dom->dom_rtattach)
  73                         dom->dom_rtattach(&table[dom->dom_family],
  74                             dom->dom_rtoffset);
  75 }
  76
  77 void
  78 route_init()
  79 {
  80         rn_init();      /* initialize all zeroes, all ones, mask table */
  81         rtable_init((void **)rt_tables);
  82 }
  83
  84 /*
  85  * Packet routing routines.
  86  */
  87 void
  88 rtalloc(ro)
  89         register struct route *ro;
  90 {
  91         rtalloc_ign(ro, 0UL);
  92 }
  93
  94 void
  95 rtalloc_ign(ro, ignore)
  96         register struct route *ro;
  97         u_long ignore;
  98 {
  99         struct rtentry *rt;
 100         int s;
 101
 102         if ((rt = ro->ro_rt) != NULL) {
 103                 if (rt->rt_ifp != NULL && rt->rt_flags & RTF_UP)
 104                         return;
 105                 /* XXX - We are probably always at splnet here already. */
 106                 s = splnet();
 107                 RTFREE(rt);
 108                 ro->ro_rt = NULL;
 109                 splx(s);
 110         }
 111         ro->ro_rt = rtalloc1(&ro->ro_dst, 1, ignore);
 112 }
 113
 114 /*
 115  * Look up the route that matches the address given
 116  * Or, at least try.. Create a cloned route if needed.
 117  */
 118 struct rtentry *
 119 rtalloc1(dst, report, ignflags)
 120         register struct sockaddr *dst;
 121         int report;
 122         u_long ignflags;
 123 {
 124         register struct radix_node_head *rnh = rt_tables[dst->sa_family];
 125         register struct rtentry *rt;
 126         register struct radix_node *rn;
 127         struct rtentry *newrt = 0;
 128         struct rt_addrinfo info;
 129         u_long nflags;
 130         int  s = splnet(), err = 0, msgtype = RTM_MISS;
 131
 132         /*
 133          * Look up the address in the table for that Address Family
 134          */
 135         if (rnh && (rn = rnh->rnh_matchaddr((caddr_t)dst, rnh)) &&
 136             ((rn->rn_flags & RNF_ROOT) == 0)) {
 137                 /*
 138                  * If we find it and it's not the root node, then
 139                  * get a refernce on the rtentry associated.
 140                  */
 141                 newrt = rt = (struct rtentry *)rn;
 142                 nflags = rt->rt_flags & ~ignflags;
 143                 if (report && (nflags & (RTF_CLONING | RTF_PRCLONING))) {
 144                         /*
 145                          * We are apparently adding (report = 0 in delete).
 146                          * If it requires that it be cloned, do so.
 147                          * (This implies it wasn't a HOST route.)
 148                          */
 149                         err = rtrequest(RTM_RESOLVE, dst, SA(0),
 150                                               SA(0), 0, &newrt);
 151                         if (err) {
 152                                 /*
 153                                  * If the cloning didn't succeed, maybe
 154                                  * what we have will do. Return that.
 155                                  */
 156                                 newrt = rt;
 157                                 rt->rt_refcnt++;
 158                                 goto miss;
 159                         }
 160                         if ((rt = newrt) && (rt->rt_flags & RTF_XRESOLVE)) {
 161                                 /*
 162                                  * If the new route specifies it be
 163                                  * externally resolved, then go do that.
 164                                  */
 165                                 msgtype = RTM_RESOLVE;
 166                                 goto miss;
 167                         }
 168                         /* Inform listeners of the new route. */
 169                         bzero(&info, sizeof(info));
 170                         info.rti_info[RTAX_DST] = rt_key(rt);
 171                         info.rti_info[RTAX_NETMASK] = rt_mask(rt);
 172                         info.rti_info[RTAX_GATEWAY] = rt->rt_gateway;
 173                         if (rt->rt_ifp != NULL) {
 174                                 info.rti_info[RTAX_IFP] =
 175                                     TAILQ_FIRST(&rt->rt_ifp->if_addrhead)->ifa_addr;
 176                                 info.rti_info[RTAX_IFA] = rt->rt_ifa->ifa_addr;
 177                         }
 178                         rt_missmsg(RTM_ADD, &info, rt->rt_flags, 0);
 179                 } else
 180                         rt->rt_refcnt++;
 181         } else {
 182                 /*
 183                  * Either we hit the root or couldn't find any match,
 184                  * Which basically means
 185                  * "caint get there frm here"
 186                  */
 187                 rtstat.rts_unreach++;
 188         miss:   if (report) {
 189                         /*
 190                          * If required, report the failure to the supervising
 191                          * Authorities.
 192                          * For a delete, this is not an error. (report == 0)
 193                          */
 194                         bzero((caddr_t)&info, sizeof(info));
 195                         info.rti_info[RTAX_DST] = dst;
 196                         rt_missmsg(msgtype, &info, 0, err);
 197                 }
 198         }
 199         splx(s);
 200         return (newrt);
 201 }
 202
 203 /*
 204  * Remove a reference count from an rtentry.
 205  * If the count gets low enough, take it out of the routing table
 206  */
 207 void
 208 rtfree(rt)
 209         register struct rtentry *rt;
 210 {
 211         /*
 212          * find the tree for that address family
 213          */
 214         register struct radix_node_head *rnh =
 215                 rt_tables[rt_key(rt)->sa_family];
 216         register struct ifaddr *ifa;
 217
 218         if (rt == 0 || rnh == 0)
 219                 panic("rtfree");
 220
 221         /*
 222          * decrement the reference count by one and if it reaches 0,
 223          * and there is a close function defined, call the close function
 224          */
 225         rt->rt_refcnt--;
 226         if(rnh->rnh_close && rt->rt_refcnt == 0) {
 227                 rnh->rnh_close((struct radix_node *)rt, rnh);
 228         }
 229
 230         /*
 231          * If we are no longer "up" (and ref == 0)
 232          * then we can free the resources associated
 233          * with the route.
 234          */
 235         if (rt->rt_refcnt <= 0 && (rt->rt_flags & RTF_UP) == 0) {
 236                 if (rt->rt_nodes->rn_flags & (RNF_ACTIVE | RNF_ROOT))
 237                         panic ("rtfree 2");
 238                 /*
 239                  * the rtentry must have been removed from the routing table
 240                  * so it is represented in rttrash.. remove that now.
 241                  */
 242                 rttrash--;
 243
 244 #ifdef  DIAGNOSTIC
 245                 if (rt->rt_refcnt < 0) {
 246                         printf("rtfree: %p not freed (neg refs)\n", rt);
 247                         return;
 248                 }
 249 #endif
 250
 251                 /*
 252                  * release references on items we hold them on..
 253                  * e.g other routes and ifaddrs.
 254                  */
 255                 if((ifa = rt->rt_ifa))
 256                         IFAFREE(ifa);
 257                 if (rt->rt_parent) {
 258                         RTFREE(rt->rt_parent);
 259                 }
 260
 261                 /*
 262                  * The key is separatly alloc'd so free it (see rt_setgate()).
 263                  * This also frees the gateway, as they are always malloc'd
 264                  * together.
 265                  */
 266                 Free(rt_key(rt));
 267
 268                 /*
 269                  * and the rtentry itself of course
 270                  */
 271                 Free(rt);
 272         }
 273 }
 274
 275 void
 276 ifafree(ifa)
 277         register struct ifaddr *ifa;
 278 {
 279         if (ifa == NULL)
 280                 panic("ifafree");
 281         if (ifa->ifa_refcnt == 0)
 282                 free(ifa, M_IFADDR);
 283         else
 284                 ifa->ifa_refcnt--;
 285 }
 286
 287 /*
 288  * Force a routing table entry to the specified
 289  * destination to go through the given gateway.
 290  * Normally called as a result of a routing redirect
 291  * message from the network layer.
 292  *
 293  * N.B.: must be called at splnet
 294  *
 295  */
 296 void
 297 rtredirect(dst, gateway, netmask, flags, src, rtp)
 298         struct sockaddr *dst, *gateway, *netmask, *src;
 299         int flags;
 300         struct rtentry **rtp;
 301 {
 302         struct rtentry *rt;
 303         int error = 0;
 304         short *stat = 0;
 305         struct rt_addrinfo info;
 306         struct ifaddr *ifa;
 307
 308         /* verify the gateway is directly reachable */
 309         if ((ifa = ifa_ifwithnet(gateway)) == 0) {
 310                 error = ENETUNREACH;
 311                 goto out;
 312         }
 313         rt = rtalloc1(dst, 0, 0UL);
 314         /*
 315          * If the redirect isn't from our current router for this dst,
 316          * it's either old or wrong.  If it redirects us to ourselves,
 317          * we have a routing loop, perhaps as a result of an interface
 318          * going down recently.
 319          */
 320 #define equal(a1, a2) (bcmp((caddr_t)(a1), (caddr_t)(a2), (a1)->sa_len) == 0)
 321         if (!(flags & RTF_DONE) && rt &&
 322              (!equal(src, rt->rt_gateway) || rt->rt_ifa != ifa))
 323                 error = EINVAL;
 324         else if (ifa_ifwithaddr(gateway))
 325                 error = EHOSTUNREACH;
 326         if (error)
 327                 goto done;
 328         /*
 329          * Create a new entry if we just got back a wildcard entry
 330          * or the the lookup failed.  This is necessary for hosts
 331          * which use routing redirects generated by smart gateways
 332          * to dynamically build the routing tables.
 333          */
 334         if ((rt == 0) || (rt_mask(rt) && rt_mask(rt)->sa_len < 2))
 335                 goto create;
 336         /*
 337          * Don't listen to the redirect if it's
 338          * for a route to an interface.
 339          */
 340         if (rt->rt_flags & RTF_GATEWAY) {
 341                 if (((rt->rt_flags & RTF_HOST) == 0) && (flags & RTF_HOST)) {
 342                         /*
 343                          * Changing from route to net => route to host.
 344                          * Create new route, rather than smashing route to net.
 345                          */
 346                 create:
 347                         if (rt)
 348                                 rtfree(rt);
 349                         flags |=  RTF_GATEWAY | RTF_DYNAMIC;
 350                         bzero((caddr_t)&info, sizeof(info));
 351                         info.rti_info[RTAX_DST] = dst;
 352                         info.rti_info[RTAX_GATEWAY] = gateway;
 353                         info.rti_info[RTAX_NETMASK] = netmask;
 354                         info.rti_ifa = ifa;
 355                         info.rti_flags = flags;
 356                         rt = NULL;
 357                         error = rtrequest1(RTM_ADD, &info, &rt);
 358                         if (rt != NULL)
 359                                 flags = rt->rt_flags;
 360                         stat = &rtstat.rts_dynamic;
 361                 } else {
 362                         /*
 363                          * Smash the current notion of the gateway to
 364                          * this destination.  Should check about netmask!!!
 365                          */
 366                         rt->rt_flags |= RTF_MODIFIED;
 367                         flags |= RTF_MODIFIED;
 368                         stat = &rtstat.rts_newgateway;
 369                         /*
 370                          * add the key and gateway (in one malloc'd chunk).
 371                          */
 372                         rt_setgate(rt, rt_key(rt), gateway);
 373                 }
 374         } else
 375                 error = EHOSTUNREACH;
 376 done:
 377         if (rt) {
 378                 if (rtp && !error)
 379                         *rtp = rt;
 380                 else
 381                         rtfree(rt);
 382         }
 383 out:
 384         if (error)
 385                 rtstat.rts_badredirect++;
 386         else if (stat != NULL)
 387                 (*stat)++;
 388         bzero((caddr_t)&info, sizeof(info));
 389         info.rti_info[RTAX_DST] = dst;
 390         info.rti_info[RTAX_GATEWAY] = gateway;
 391         info.rti_info[RTAX_NETMASK] = netmask;
 392         info.rti_info[RTAX_AUTHOR] = src;
 393         rt_missmsg(RTM_REDIRECT, &info, flags, error);
 394 }
 395
 396 /*
 397 * Routing table ioctl interface.
 398 */
 399 int
 400 rtioctl(req, data, p)
 401         u_long req;
 402         caddr_t data;
 403         struct proc *p;
 404 {
 405 #ifdef INET
 406         /* Multicast goop, grrr... */
 407         return mrt_ioctl ? mrt_ioctl(req, data) : EOPNOTSUPP;
 408 #else /* INET */
 409         return ENXIO;
 410 #endif /* INET */
 411 }
 412
 413 struct ifaddr *
 414 ifa_ifwithroute(flags, dst, gateway)
 415         int flags;
 416         struct sockaddr *dst, *gateway;
 417 {
 418         register struct ifaddr *ifa;
 419         if ((flags & RTF_GATEWAY) == 0) {
 420                 /*
 421                  * If we are adding a route to an interface,
 422                  * and the interface is a pt to pt link
 423                  * we should search for the destination
 424                  * as our clue to the interface.  Otherwise
 425                  * we can use the local address.
 426                  */
 427                 ifa = 0;
 428                 if (flags & RTF_HOST) {
 429                         ifa = ifa_ifwithdstaddr(dst);
 430                 }
 431                 if (ifa == 0)
 432                         ifa = ifa_ifwithaddr(gateway);
 433         } else {
 434                 /*
 435                  * If we are adding a route to a remote net
 436                  * or host, the gateway may still be on the
 437                  * other end of a pt to pt link.
 438                  */
 439                 ifa = ifa_ifwithdstaddr(gateway);
 440         }
 441         if (ifa == 0)
 442                 ifa = ifa_ifwithnet(gateway);
 443         if (ifa == 0) {
 444                 struct rtentry *rt = rtalloc1(gateway, 0, 0UL);
 445                 if (rt == 0)
 446                         return (0);
 447                 rt->rt_refcnt--;
 448                 if ((ifa = rt->rt_ifa) == 0)
 449                         return (0);
 450         }
 451         if (ifa->ifa_addr->sa_family != dst->sa_family) {
 452                 struct ifaddr *oifa = ifa;
 453                 ifa = ifaof_ifpforaddr(dst, ifa->ifa_ifp);
 454                 if (ifa == 0)
 455                         ifa = oifa;
 456         }
 457         return (ifa);
 458 }
 459
 460 static int rt_fixdelete __P((struct radix_node *, void *));
 461 static int rt_fixchange __P((struct radix_node *, void *));
 462
 463 struct rtfc_arg {
 464         struct rtentry *rt0;
 465         struct radix_node_head *rnh;
 466 };
 467
 468 /*
 469  * Do appropriate manipulations of a routing tree given
 470  * all the bits of info needed
 471  */
 472 int
 473 rtrequest(req, dst, gateway, netmask, flags, ret_nrt)
 474         int req, flags;
 475         struct sockaddr *dst, *gateway, *netmask;
 476         struct rtentry **ret_nrt;
 477 {
 478         struct rt_addrinfo info;
 479
 480         bzero((caddr_t)&info, sizeof(info));
 481         info.rti_flags = flags;
 482         info.rti_info[RTAX_DST] = dst;
 483         info.rti_info[RTAX_GATEWAY] = gateway;
 484         info.rti_info[RTAX_NETMASK] = netmask;
 485         return rtrequest1(req, &info, ret_nrt);
 486 }
 487
 488 /*
 489  * These (questionable) definitions of apparent local variables apply
 490  * to the next two functions.  XXXXXX!!!
 491  */
 492 #define dst     info->rti_info[RTAX_DST]
 493 #define gateway info->rti_info[RTAX_GATEWAY]
 494 #define netmask info->rti_info[RTAX_NETMASK]
 495 #define ifaaddr info->rti_info[RTAX_IFA]
 496 #define ifpaddr info->rti_info[RTAX_IFP]
 497 #define flags   info->rti_flags
 498
 499 int
 500 rt_getifa(info)
 501         struct rt_addrinfo *info;
 502 {
 503         struct ifaddr *ifa;
 504         int error = 0;
 505
 506         /*
 507          * ifp may be specified by sockaddr_dl
 508          * when protocol address is ambiguous.
 509          */
 510         if (info->rti_ifp == NULL && ifpaddr != NULL &&
 511             ifpaddr->sa_family == AF_LINK &&
 512             (ifa = ifa_ifwithnet(ifpaddr)) != NULL)
 513                 info->rti_ifp = ifa->ifa_ifp;
 514         if (info->rti_ifa == NULL && ifaaddr != NULL)
 515                 info->rti_ifa = ifa_ifwithaddr(ifaaddr);
 516         if (info->rti_ifa == NULL) {
 517                 struct sockaddr *sa;
 518
 519                 sa = ifaaddr != NULL ? ifaaddr :
 520                     (gateway != NULL ? gateway : dst);
 521                 if (sa != NULL && info->rti_ifp != NULL)
 522                         info->rti_ifa = ifaof_ifpforaddr(sa, info->rti_ifp);
 523                 else if (dst != NULL && gateway != NULL)
 524                         info->rti_ifa = ifa_ifwithroute(flags, dst, gateway);
 525                 else if (sa != NULL)
 526                         info->rti_ifa = ifa_ifwithroute(flags, sa, sa);
 527         }
 528         if ((ifa = info->rti_ifa) != NULL) {
 529                 if (info->rti_ifp == NULL)
 530                         info->rti_ifp = ifa->ifa_ifp;
 531         } else
 532                 error = ENETUNREACH;
 533         return (error);
 534 }
 535
 536 int
 537 rtrequest1(req, info, ret_nrt)
 538         int req;
 539         struct rt_addrinfo *info;
 540         struct rtentry **ret_nrt;
 541 {
 542         int s = splnet(); int error = 0;
 543         register struct rtentry *rt;
 544         register struct radix_node *rn;
 545         register struct radix_node_head *rnh;
 546         struct ifaddr *ifa;
 547         struct sockaddr *ndst;
 548 #define senderr(x) { error = x ; goto bad; }
 549
 550         /*
 551          * Find the correct routing tree to use for this Address Family
 552          */
 553         if ((rnh = rt_tables[dst->sa_family]) == 0)
 554                 senderr(EAFNOSUPPORT);
 555         /*
 556          * If we are adding a host route then we don't want to put
 557          * a netmask in the tree, nor do we want to clone it.
 558          */
 559         if (flags & RTF_HOST) {
 560                 netmask = 0;
 561                 flags &= ~(RTF_CLONING | RTF_PRCLONING);
 562         }
 563         switch (req) {
 564         case RTM_DELETE:
 565                 /*
 566                  * Remove the item from the tree and return it.
 567                  * Complain if it is not there and do no more processing.
 568                  */
 569                 if ((rn = rnh->rnh_deladdr(dst, netmask, rnh)) == 0)
 570                         senderr(ESRCH);
 571                 if (rn->rn_flags & (RNF_ACTIVE | RNF_ROOT))
 572                         panic ("rtrequest delete");
 573                 rt = (struct rtentry *)rn;
 574
 575                 /*
 576                  * Now search what's left of the subtree for any cloned
 577                  * routes which might have been formed from this node.
 578                  */
 579                 if ((rt->rt_flags & (RTF_CLONING | RTF_PRCLONING)) &&
 580                     rt_mask(rt)) {
 581                         rnh->rnh_walktree_from(rnh, dst, rt_mask(rt),
 582                                                rt_fixdelete, rt);
 583                 }
 584
 585                 /*
 586                  * Remove any external references we may have.
 587                  * This might result in another rtentry being freed if
 588                  * we held its last reference.
 589                  */
 590                 if (rt->rt_gwroute) {
 591                         rt = rt->rt_gwroute;
 592                         RTFREE(rt);
 593                         (rt = (struct rtentry *)rn)->rt_gwroute = 0;
 594                 }
 595
 596                 /*
 597                  * NB: RTF_UP must be set during the search above,
 598                  * because we might delete the last ref, causing
 599                  * rt to get freed prematurely.
 600                  *  eh? then why not just add a reference?
 601                  * I'm not sure how RTF_UP helps matters. (JRE)
 602                  */
 603                 rt->rt_flags &= ~RTF_UP;
 604
 605                 /*
 606                  * give the protocol a chance to keep things in sync.
 607                  */
 608                 if ((ifa = rt->rt_ifa) && ifa->ifa_rtrequest)
 609                         ifa->ifa_rtrequest(RTM_DELETE, rt, info);
 610
 611                 /*
 612                  * one more rtentry floating around that is not
 613                  * linked to the routing table.
 614                  */
 615                 rttrash++;
 616
 617                 /*
 618                  * If the caller wants it, then it can have it,
 619                  * but it's up to it to free the rtentry as we won't be
 620                  * doing it.
 621                  */
 622                 if (ret_nrt)
 623                         *ret_nrt = rt;
 624                 else if (rt->rt_refcnt <= 0) {
 625                         rt->rt_refcnt++; /* make a 1->0 transition */
 626                         rtfree(rt);
 627                 }
 628                 break;
 629
 630         case RTM_RESOLVE:
 631                 if (ret_nrt == 0 || (rt = *ret_nrt) == 0)
 632                         senderr(EINVAL);
 633                 ifa = rt->rt_ifa;
 634                 flags = rt->rt_flags &
 635                     ~(RTF_CLONING | RTF_PRCLONING | RTF_STATIC);
 636                 flags |= RTF_WASCLONED;
 637                 gateway = rt->rt_gateway;
 638                 if ((netmask = rt->rt_genmask) == 0)
 639                         flags |= RTF_HOST;
 640                 goto makeroute;
 641
 642         case RTM_ADD:
 643                 if ((flags & RTF_GATEWAY) && !gateway)
 644                         panic("rtrequest: GATEWAY but no gateway");
 645
 646                 if (info->rti_ifa == NULL && (error = rt_getifa(info)))
 647                         senderr(error);
 648                 ifa = info->rti_ifa;
 649
 650         makeroute:
 651                 R_Malloc(rt, struct rtentry *, sizeof(*rt));
 652                 if (rt == 0)
 653                         senderr(ENOBUFS);
 654                 Bzero(rt, sizeof(*rt));
 655                 rt->rt_flags = RTF_UP | flags;
 656                 /*
 657                  * Add the gateway. Possibly re-malloc-ing the storage for it
 658                  * also add the rt_gwroute if possible.
 659                  */
 660                 if ((error = rt_setgate(rt, dst, gateway)) != 0) {
 661                         Free(rt);
 662                         senderr(error);
 663                 }
 664
 665                 /*
 666                  * point to the (possibly newly malloc'd) dest address.
 667                  */
 668                 ndst = rt_key(rt);
 669
 670                 /*
 671                  * make sure it contains the value we want (masked if needed).
 672                  */
 673                 if (netmask) {
 674                         rt_maskedcopy(dst, ndst, netmask);
 675                 } else
 676                         Bcopy(dst, ndst, dst->sa_len);
 677
 678                 /*
 679                  * Note that we now have a reference to the ifa.
 680                  * This moved from below so that rnh->rnh_addaddr() can
 681                  * examine the ifa and  ifa->ifa_ifp if it so desires.
 682                  */
 683                 ifa->ifa_refcnt++;
 684                 rt->rt_ifa = ifa;
 685                 rt->rt_ifp = ifa->ifa_ifp;
 686                 /* XXX mtu manipulation will be done in rnh_addaddr -- itojun */
 687
 688                 rn = rnh->rnh_addaddr((caddr_t)ndst, (caddr_t)netmask,
 689                                         rnh, rt->rt_nodes);
 690                 if (rn == 0) {
 691                         struct rtentry *rt2;
 692                         /*
 693                          * Uh-oh, we already have one of these in the tree.
 694                          * We do a special hack: if the route that's already
 695                          * there was generated by the protocol-cloning
 696                          * mechanism, then we just blow it away and retry
 697                          * the insertion of the new one.
 698                          */
 699                         rt2 = rtalloc1(dst, 0, RTF_PRCLONING);
 700                         if (rt2 && rt2->rt_parent) {
 701                                 rtrequest(RTM_DELETE,
 702                                           (struct sockaddr *)rt_key(rt2),
 703                                           rt2->rt_gateway,
 704                                           rt_mask(rt2), rt2->rt_flags, 0);
 705                                 RTFREE(rt2);
 706                                 rn = rnh->rnh_addaddr((caddr_t)ndst,
 707                                                       (caddr_t)netmask,
 708                                                       rnh, rt->rt_nodes);
 709                         } else if (rt2) {
 710                                 /* undo the extra ref we got */
 711                                 RTFREE(rt2);
 712                         }
 713                 }
 714
 715                 /*
 716                  * If it still failed to go into the tree,
 717                  * then un-make it (this should be a function)
 718                  */
 719                 if (rn == 0) {
 720                         if (rt->rt_gwroute)
 721                                 rtfree(rt->rt_gwroute);
 722                         if (rt->rt_ifa) {
 723                                 IFAFREE(rt->rt_ifa);
 724                         }
 725                         Free(rt_key(rt));
 726                         Free(rt);
 727                         senderr(EEXIST);
 728                 }
 729
 730                 rt->rt_parent = 0;
 731
 732                 /*
 733                  * If we got here from RESOLVE, then we are cloning
 734                  * so clone the rest, and note that we
 735                  * are a clone (and increment the parent's references)
 736                  */
 737                 if (req == RTM_RESOLVE) {
 738                         rt->rt_rmx = (*ret_nrt)->rt_rmx; /* copy metrics */
 739                         rt->rt_rmx.rmx_pksent = 0; /* reset packet counter */
 740                         if ((*ret_nrt)->rt_flags & (RTF_CLONING | RTF_PRCLONING)) {
 741                                 rt->rt_parent = (*ret_nrt);
 742                                 (*ret_nrt)->rt_refcnt++;
 743                         }
 744                 }
 745
 746                 /*
 747                  * if this protocol has something to add to this then
 748                  * allow it to do that as well.
 749                  */
 750                 if (ifa->ifa_rtrequest)
 751                         ifa->ifa_rtrequest(req, rt, info);
 752
 753                 /*
 754                  * We repeat the same procedure from rt_setgate() here because
 755                  * it doesn't fire when we call it there because the node
 756                  * hasn't been added to the tree yet.
 757                  */
 758                 if (req == RTM_ADD &&
 759                     !(rt->rt_flags & RTF_HOST) && rt_mask(rt) != 0) {
 760                         struct rtfc_arg arg;
 761                         arg.rnh = rnh;
 762                         arg.rt0 = rt;
 763                         rnh->rnh_walktree_from(rnh, rt_key(rt), rt_mask(rt),
 764                                                rt_fixchange, &arg);
 765                 }
 766
 767                 /*
 768                  * actually return a resultant rtentry and
 769                  * give the caller a single reference.
 770                  */
 771                 if (ret_nrt) {
 772                         *ret_nrt = rt;
 773                         rt->rt_refcnt++;
 774                 }
 775                 break;
 776         default:
 777                 error = EOPNOTSUPP;
 778         }
 779 bad:
 780         splx(s);
 781         return (error);
 782 #undef dst
 783 #undef gateway
 784 #undef netmask
 785 #undef ifaaddr
 786 #undef ifpaddr
 787 #undef flags
 788 }
 789
 790 /*
 791  * Called from rtrequest(RTM_DELETE, ...) to fix up the route's ``family''
 792  * (i.e., the routes related to it by the operation of cloning).  This
 793  * routine is iterated over all potential former-child-routes by way of
 794  * rnh->rnh_walktree_from() above, and those that actually are children of
 795  * the late parent (passed in as VP here) are themselves deleted.
 796  */
 797 static int
 798 rt_fixdelete(rn, vp)
 799         struct radix_node *rn;
 800         void *vp;
 801 {
 802         struct rtentry *rt = (struct rtentry *)rn;
 803         struct rtentry *rt0 = vp;
 804
 805         if (rt->rt_parent == rt0 &&
 806             !(rt->rt_flags & (RTF_PINNED | RTF_CLONING | RTF_PRCLONING))) {
 807                 return rtrequest(RTM_DELETE, rt_key(rt),
 808                                  (struct sockaddr *)0, rt_mask(rt),
 809                                  rt->rt_flags, (struct rtentry **)0);
 810         }
 811         return 0;
 812 }
 813
 814 /*
 815  * This routine is called from rt_setgate() to do the analogous thing for
 816  * adds and changes.  There is the added complication in this case of a
 817  * middle insert; i.e., insertion of a new network route between an older
 818  * network route and (cloned) host routes.  For this reason, a simple check
 819  * of rt->rt_parent is insufficient; each candidate route must be tested
 820  * against the (mask, value) of the new route (passed as before in vp)
 821  * to see if the new route matches it.
 822  *
 823  * XXX - it may be possible to do fixdelete() for changes and reserve this
 824  * routine just for adds.  I'm not sure why I thought it was necessary to do
 825  * changes this way.
 826  */
 827 #ifdef DEBUG
 828 static int rtfcdebug = 0;
 829 #endif
 830
 831 static int
 832 rt_fixchange(rn, vp)
 833         struct radix_node *rn;
 834         void *vp;
 835 {
 836         struct rtentry *rt = (struct rtentry *)rn;
 837         struct rtfc_arg *ap = vp;
 838         struct rtentry *rt0 = ap->rt0;
 839         struct radix_node_head *rnh = ap->rnh;
 840         u_char *xk1, *xm1, *xk2, *xmp;
 841         int i, len, mlen;
 842
 843 #ifdef DEBUG
 844         if (rtfcdebug)
 845                 printf("rt_fixchange: rt %p, rt0 %p\n", rt, rt0);
 846 #endif
 847
 848         if (!rt->rt_parent ||
 849             (rt->rt_flags & (RTF_PINNED | RTF_CLONING | RTF_PRCLONING))) {
 850 #ifdef DEBUG
 851                 if(rtfcdebug) printf("no parent, pinned or cloning\n");
 852 #endif
 853                 return 0;
 854         }
 855
 856         if (rt->rt_parent == rt0) {
 857 #ifdef DEBUG
 858                 if(rtfcdebug) printf("parent match\n");
 859 #endif
 860                 return rtrequest(RTM_DELETE, rt_key(rt),
 861                                  (struct sockaddr *)0, rt_mask(rt),
 862                                  rt->rt_flags, (struct rtentry **)0);
 863         }
 864
 865         /*
 866          * There probably is a function somewhere which does this...
 867          * if not, there should be.
 868          */
 869         len = imin(((struct sockaddr *)rt_key(rt0))->sa_len,
 870                    ((struct sockaddr *)rt_key(rt))->sa_len);
 871
 872         xk1 = (u_char *)rt_key(rt0);
 873         xm1 = (u_char *)rt_mask(rt0);
 874         xk2 = (u_char *)rt_key(rt);
 875
 876         /* avoid applying a less specific route */
 877         xmp = (u_char *)rt_mask(rt->rt_parent);
 878         mlen = ((struct sockaddr *)rt_key(rt->rt_parent))->sa_len;
 879         if (mlen > ((struct sockaddr *)rt_key(rt0))->sa_len) {
 880 #ifdef DEBUG
 881                 if (rtfcdebug)
 882                         printf("rt_fixchange: inserting a less "
 883                                "specific route\n");
 884 #endif
 885                 return 0;
 886         }
 887         for (i = rnh->rnh_treetop->rn_offset; i < mlen; i++) {
 888                 if ((xmp[i] & ~(xmp[i] ^ xm1[i])) != xmp[i]) {
 889 #ifdef DEBUG
 890                         if (rtfcdebug)
 891                                 printf("rt_fixchange: inserting a less "
 892                                        "specific route\n");
 893 #endif
 894                         return 0;
 895                 }
 896         }
 897
 898         for (i = rnh->rnh_treetop->rn_offset; i < len; i++) {
 899                 if ((xk2[i] & xm1[i]) != xk1[i]) {
 900 #ifdef DEBUG
 901                         if(rtfcdebug) printf("no match\n");
 902 #endif
 903                         return 0;
 904                 }
 905         }
 906
 907         /*
 908          * OK, this node is a clone, and matches the node currently being
 909          * changed/added under the node's mask.  So, get rid of it.
 910          */
 911 #ifdef DEBUG
 912         if(rtfcdebug) printf("deleting\n");
 913 #endif
 914         return rtrequest(RTM_DELETE, rt_key(rt), (struct sockaddr *)0,
 915                          rt_mask(rt), rt->rt_flags, (struct rtentry **)0);
 916 }
 917
 918 #define ROUNDUP(a) (a>0 ? (1 + (((a) - 1) | (sizeof(long) - 1))) : sizeof(long))
 919
 920 int
 921 rt_setgate(rt0, dst, gate)
 922         struct rtentry *rt0;
 923         struct sockaddr *dst, *gate;
 924 {
 925         caddr_t new, old;
 926         int dlen = ROUNDUP(dst->sa_len), glen = ROUNDUP(gate->sa_len);
 927         register struct rtentry *rt = rt0;
 928         struct radix_node_head *rnh = rt_tables[dst->sa_family];
 929
 930         /*
 931          * A host route with the destination equal to the gateway
 932          * will interfere with keeping LLINFO in the routing
 933          * table, so disallow it.
 934          */
 935         if (((rt0->rt_flags & (RTF_HOST|RTF_GATEWAY|RTF_LLINFO)) ==
 936                                         (RTF_HOST|RTF_GATEWAY)) &&
 937             (dst->sa_len == gate->sa_len) &&
 938             (bcmp(dst, gate, dst->sa_len) == 0)) {
 939                 /*
 940                  * The route might already exist if this is an RTM_CHANGE
 941                  * or a routing redirect, so try to delete it.
 942                  */
 943                 if (rt_key(rt0))
 944                         rtrequest(RTM_DELETE, (struct sockaddr *)rt_key(rt0),
 945                             rt0->rt_gateway, rt_mask(rt0), rt0->rt_flags, 0);
 946                 return EADDRNOTAVAIL;
 947         }
 948
 949         /*
 950          * Both dst and gateway are stored in the same malloc'd chunk
 951          * (If I ever get my hands on....)
 952          * if we need to malloc a new chunk, then keep the old one around
 953          * till we don't need it any more.
 954          */
 955         if (rt->rt_gateway == 0 || glen > ROUNDUP(rt->rt_gateway->sa_len)) {
 956                 old = (caddr_t)rt_key(rt);
 957                 R_Malloc(new, caddr_t, dlen + glen);
 958                 if (new == 0)
 959                         return ENOBUFS;
 960                 rt->rt_nodes->rn_key = new;
 961         } else {
 962                 /*
 963                  * otherwise just overwrite the old one
 964                  */
 965                 new = rt->rt_nodes->rn_key;
 966                 old = 0;
 967         }
 968
 969         /*
 970          * copy the new gateway value into the memory chunk
 971          */
 972         Bcopy(gate, (rt->rt_gateway = (struct sockaddr *)(new + dlen)), glen);
 973
 974         /*
 975          * if we are replacing the chunk (or it's new) we need to
 976          * replace the dst as well
 977          */
 978         if (old) {
 979                 Bcopy(dst, new, dlen);
 980                 Free(old);
 981         }
 982
 983         /*
 984          * If there is already a gwroute, it's now almost definitly wrong
 985          * so drop it.
 986          */
 987         if (rt->rt_gwroute != NULL) {
 988                 RTFREE(rt->rt_gwroute);
 989                 rt->rt_gwroute = NULL;
 990         }
 991         /*
 992          * Cloning loop avoidance:
 993          * In the presence of protocol-cloning and bad configuration,
 994          * it is possible to get stuck in bottomless mutual recursion
 995          * (rtrequest rt_setgate rtalloc1).  We avoid this by not allowing
 996          * protocol-cloning to operate for gateways (which is probably the
 997          * correct choice anyway), and avoid the resulting reference loops
 998          * by disallowing any route to run through itself as a gateway.
 999          * This is obviously mandatory when we get rt->rt_output().
1000          */
1001         if (rt->rt_flags & RTF_GATEWAY) {
1002                 rt->rt_gwroute = rtalloc1(gate, 1, RTF_PRCLONING);
1003                 if (rt->rt_gwroute == rt) {
1004                         RTFREE(rt->rt_gwroute);
1005                         rt->rt_gwroute = 0;
1006                         return EDQUOT; /* failure */
1007                 }
1008         }
1009
1010         /*
1011          * This isn't going to do anything useful for host routes, so
1012          * don't bother.  Also make sure we have a reasonable mask
1013          * (we don't yet have one during adds).
1014          */
1015         if (!(rt->rt_flags & RTF_HOST) && rt_mask(rt) != 0) {
1016                 struct rtfc_arg arg;
1017                 arg.rnh = rnh;
1018                 arg.rt0 = rt;
1019                 rnh->rnh_walktree_from(rnh, rt_key(rt), rt_mask(rt),
1020                                        rt_fixchange, &arg);
1021         }
1022
1023         return 0;
1024 }
1025
1026 static void
1027 rt_maskedcopy(src, dst, netmask)
1028         struct sockaddr *src, *dst, *netmask;
1029 {
1030         register u_char *cp1 = (u_char *)src;
1031         register u_char *cp2 = (u_char *)dst;
1032         register u_char *cp3 = (u_char *)netmask;
1033         u_char *cplim = cp2 + *cp3;
1034         u_char *cplim2 = cp2 + *cp1;
1035
1036         *cp2++ = *cp1++; *cp2++ = *cp1++; /* copies sa_len & sa_family */
1037         cp3 += 2;
1038         if (cplim > cplim2)
1039                 cplim = cplim2;
1040         while (cp2 < cplim)
1041                 *cp2++ = *cp1++ & *cp3++;
1042         if (cp2 < cplim2)
1043                 bzero((caddr_t)cp2, (unsigned)(cplim2 - cp2));
1044 }
1045
1046 /*
1047  * Set up a routing table entry, normally
1048  * for an interface.
1049  */
1050 int
1051 rtinit(ifa, cmd, flags)
1052         register struct ifaddr *ifa;
1053         int cmd, flags;
1054 {
1055         register struct rtentry *rt;
1056         register struct sockaddr *dst;
1057         register struct sockaddr *deldst;
1058         struct sockaddr *netmask;
1059         struct mbuf *m = 0;
1060         struct rtentry *nrt = 0;
1061         struct radix_node_head *rnh;
1062         struct radix_node *rn;
1063         int error;
1064         struct rt_addrinfo info;
1065
1066         if (flags & RTF_HOST) {
1067                 dst = ifa->ifa_dstaddr;
1068                 netmask = NULL;
1069         } else {
1070                 dst = ifa->ifa_addr;
1071                 netmask = ifa->ifa_netmask;
1072         }
1073         /*
1074          * If it's a delete, check that if it exists, it's on the correct
1075          * interface or we might scrub a route to another ifa which would
1076          * be confusing at best and possibly worse.
1077          */
1078         if (cmd == RTM_DELETE) {
1079                 /*
1080                  * It's a delete, so it should already exist..
1081                  * If it's a net, mask off the host bits
1082                  * (Assuming we have a mask)
1083                  */
1084                 if (netmask != NULL) {
1085                         m = m_get(M_DONTWAIT, MT_SONAME);
1086                         if (m == NULL)
1087                                 return(ENOBUFS);
1088                         deldst = mtod(m, struct sockaddr *);
1089                         rt_maskedcopy(dst, deldst, netmask);
1090                         dst = deldst;
1091                 }
1092                 /*
1093                  * Look up an rtentry that is in the routing tree and
1094                  * contains the correct info.
1095                  */
1096                 if ((rnh = rt_tables[dst->sa_family]) == NULL ||
1097                     (rn = rnh->rnh_lookup(dst, netmask, rnh)) == NULL ||
1098                     (rn->rn_flags & RNF_ROOT) ||
1099                     ((struct rtentry *)rn)->rt_ifa != ifa ||
1100                     !equal(SA(rn->rn_key), dst)) {
1101                         if (m)
1102                                 (void) m_free(m);
1103                         return (flags & RTF_HOST ? EHOSTUNREACH : ENETUNREACH);
1104                 }
1105                 /* XXX */
1106 #if 0
1107                 else {
1108                         /*
1109                          * One would think that as we are deleting, and we know
1110                          * it doesn't exist, we could just return at this point
1111                          * with an "ELSE" clause, but apparently not..
1112                          */
1113                         return (flags & RTF_HOST ? EHOSTUNREACH : ENETUNREACH);
1114                 }
1115 #endif
1116         }
1117         /*
1118          * Do the actual request
1119          */
1120         bzero((caddr_t)&info, sizeof(info));
1121         info.rti_ifa = ifa;
1122         info.rti_flags = flags | ifa->ifa_flags;
1123         info.rti_info[RTAX_DST] = dst;
1124         info.rti_info[RTAX_GATEWAY] = ifa->ifa_addr;
1125         info.rti_info[RTAX_NETMASK] = netmask;
1126         error = rtrequest1(cmd, &info, &nrt);
1127         if (error == 0 && (rt = nrt) != NULL) {
1128                 /*
1129                  * notify any listening routing agents of the change
1130                  */
1131                 rt_newaddrmsg(cmd, ifa, error, rt);
1132                 if (cmd == RTM_DELETE) {
1133                         /*
1134                          * If we are deleting, and we found an entry, then
1135                          * it's been removed from the tree.. now throw it away.
1136                          */
1137                         if (rt->rt_refcnt <= 0) {
1138                                 rt->rt_refcnt++; /* make a 1->0 transition */
1139                                 rtfree(rt);
1140                         }
1141                 } else if (cmd == RTM_ADD) {
1142                         /*
1143                          * We just wanted to add it.. we don't actually
1144                          * need a reference.
1145                          */
1146                         rt->rt_refcnt--;
1147                 }
1148         }
1149         if (m)
1150                 (void) m_free(m);
1151         return (error);
1152 }
1153
1154 /* This must be before ip6_init2(), which is now SI_ORDER_MIDDLE */
1155 SYSINIT(route, SI_SUB_PROTO_DOMAIN, SI_ORDER_THIRD, route_init, 0);