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