bsd/netinet/in_rmx.c

   1 /*
   2  * Copyright (c) 2000,2007 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29  * Copyright 1994, 1995 Massachusetts Institute of Technology
  30  *
  31  * Permission to use, copy, modify, and distribute this software and
  32  * its documentation for any purpose and without fee is hereby
  33  * granted, provided that both the above copyright notice and this
  34  * permission notice appear in all copies, that both the above
  35  * copyright notice and this permission notice appear in all
  36  * supporting documentation, and that the name of M.I.T. not be used
  37  * in advertising or publicity pertaining to distribution of the
  38  * software without specific, written prior permission.  M.I.T. makes
  39  * no representations about the suitability of this software for any
  40  * purpose.  It is provided "as is" without express or implied
  41  * warranty.
  42  *
  43  * THIS SOFTWARE IS PROVIDED BY M.I.T. ``AS IS''.  M.I.T. DISCLAIMS
  44  * ALL EXPRESS OR IMPLIED WARRANTIES WITH REGARD TO THIS SOFTWARE,
  45  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
  46  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT
  47  * SHALL M.I.T. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  48  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  49  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
  50  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  51  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  52  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
  53  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  54  * SUCH DAMAGE.
  55  *
  56  * $FreeBSD: src/sys/netinet/in_rmx.c,v 1.37.2.1 2001/05/14 08:23:49 ru Exp $
  57  */
  58
  59 /*
  60  * This code does two things necessary for the enhanced TCP metrics to
  61  * function in a useful manner:
  62  *  1) It marks all non-host routes as `cloning', thus ensuring that
  63  *     every actual reference to such a route actually gets turned
  64  *     into a reference to a host route to the specific destination
  65  *     requested.
  66  *  2) When such routes lose all their references, it arranges for them
  67  *     to be deleted in some random collection of circumstances, so that
  68  *     a large quantity of stale routing data is not kept in kernel memory
  69  *     indefinitely.  See in_rtqtimo() below for the exact mechanism.
  70  */
  71
  72 #include <sys/param.h>
  73 #include <sys/systm.h>
  74 #include <sys/kernel.h>
  75 #include <sys/sysctl.h>
  76 #include <sys/socket.h>
  77 #include <sys/mbuf.h>
  78 #include <sys/syslog.h>
  79 #include <kern/lock.h>
  80
  81 #include <net/if.h>
  82 #include <net/route.h>
  83 #include <netinet/in.h>
  84 #include <netinet/in_var.h>
  85
  86 extern int tvtohz(struct timeval *);
  87 extern int      in_inithead(void **head, int off);
  88 extern u_long route_generation;
  89
  90 #ifdef __APPLE__
  91 static void in_rtqtimo(void *rock);
  92 #endif
  93
  94 #define RTPRF_OURS              RTF_PROTO3      /* set on routes we manage */
  95
  96 /*
  97  * Do what we need to do when inserting a route.
  98  */
  99 static struct radix_node *
 100 in_addroute(void *v_arg, void *n_arg, struct radix_node_head *head,
 101             struct radix_node *treenodes)
 102 {
 103         struct rtentry *rt = (struct rtentry *)treenodes;
 104         struct sockaddr_in *sin = (struct sockaddr_in *)rt_key(rt);
 105         struct radix_node *ret;
 106
 107         /*
 108          * For IP, all unicast non-host routes are automatically cloning.
 109          */
 110         if(IN_MULTICAST(ntohl(sin->sin_addr.s_addr)))
 111                 rt->rt_flags |= RTF_MULTICAST;
 112
 113         if(!(rt->rt_flags & (RTF_HOST | RTF_CLONING | RTF_MULTICAST))) {
 114                 rt->rt_flags |= RTF_PRCLONING;
 115         }
 116
 117         /*
 118          * A little bit of help for both IP output and input:
 119          *   For host routes, we make sure that RTF_BROADCAST
 120          *   is set for anything that looks like a broadcast address.
 121          *   This way, we can avoid an expensive call to in_broadcast()
 122          *   in ip_output() most of the time (because the route passed
 123          *   to ip_output() is almost always a host route).
 124          *
 125          *   We also do the same for local addresses, with the thought
 126          *   that this might one day be used to speed up ip_input().
 127          *
 128          * We also mark routes to multicast addresses as such, because
 129          * it's easy to do and might be useful (but this is much more
 130          * dubious since it's so easy to inspect the address).  (This
 131          * is done above.)
 132          */
 133         if (rt->rt_flags & RTF_HOST) {
 134                 if (in_broadcast(sin->sin_addr, rt->rt_ifp)) {
 135                         rt->rt_flags |= RTF_BROADCAST;
 136                 } else {
 137 #define satosin(sa) ((struct sockaddr_in *)sa)
 138                         if (satosin(rt->rt_ifa->ifa_addr)->sin_addr.s_addr
 139                             == sin->sin_addr.s_addr)
 140                                 rt->rt_flags |= RTF_LOCAL;
 141 #undef satosin
 142                 }
 143         }
 144
 145         if (!rt->rt_rmx.rmx_mtu && !(rt->rt_rmx.rmx_locks & RTV_MTU)
 146             && rt->rt_ifp)
 147                 rt->rt_rmx.rmx_mtu = rt->rt_ifp->if_mtu;
 148
 149         ret = rn_addroute(v_arg, n_arg, head, treenodes);
 150         if (ret == NULL && rt->rt_flags & RTF_HOST) {
 151                 struct rtentry *rt2;
 152                 /*
 153                  * We are trying to add a host route, but can't.
 154                  * Find out if it is because of an
 155                  * ARP entry and delete it if so.
 156                  */
 157                 rt2 = rtalloc1_locked((struct sockaddr *)sin, 0,
 158                                 RTF_CLONING | RTF_PRCLONING);
 159                 if (rt2) {
 160                         if (rt2->rt_flags & RTF_LLINFO &&
 161                                 rt2->rt_flags & RTF_HOST &&
 162                                 rt2->rt_gateway &&
 163                                 rt2->rt_gateway->sa_family == AF_LINK) {
 164                                 rtrequest_locked(RTM_DELETE,
 165                                           (struct sockaddr *)rt_key(rt2),
 166                                           rt2->rt_gateway,
 167                                           rt_mask(rt2), rt2->rt_flags, 0);
 168                                 ret = rn_addroute(v_arg, n_arg, head,
 169                                         treenodes);
 170                         }
 171                         rtfree_locked(rt2);
 172                 }
 173         }
 174         return ret;
 175 }
 176
 177 /*
 178  * This code is the inverse of in_clsroute: on first reference, if we
 179  * were managing the route, stop doing so and set the expiration timer
 180  * back off again.
 181  */
 182 static struct radix_node *
 183 in_matroute(void *v_arg, struct radix_node_head *head)
 184 {
 185         struct radix_node *rn = rn_match(v_arg, head);
 186         struct rtentry *rt = (struct rtentry *)rn;
 187
 188         if(rt && rt->rt_refcnt == 0) { /* this is first reference */
 189                 if(rt->rt_flags & RTPRF_OURS) {
 190                         rt->rt_flags &= ~RTPRF_OURS;
 191                         rt->rt_rmx.rmx_expire = 0;
 192                 }
 193         }
 194         return rn;
 195 }
 196
 197 static int rtq_reallyold = 60*60;
 198         /* one hour is ``really old'' */
 199 SYSCTL_INT(_net_inet_ip, IPCTL_RTEXPIRE, rtexpire, CTLFLAG_RW,
 200     &rtq_reallyold , 0,
 201     "Default expiration time on dynamically learned routes");
 202
 203 static int rtq_minreallyold = 10;
 204         /* never automatically crank down to less */
 205 SYSCTL_INT(_net_inet_ip, IPCTL_RTMINEXPIRE, rtminexpire, CTLFLAG_RW,
 206     &rtq_minreallyold , 0,
 207     "Minimum time to attempt to hold onto dynamically learned routes");
 208
 209 static int rtq_toomany = 128;
 210         /* 128 cached routes is ``too many'' */
 211 SYSCTL_INT(_net_inet_ip, IPCTL_RTMAXCACHE, rtmaxcache, CTLFLAG_RW,
 212     &rtq_toomany , 0, "Upper limit on dynamically learned routes");
 213
 214 #ifdef __APPLE__
 215 /* XXX LD11JUL02 Special case for AOL 5.1.2 connectivity issue to AirPort BS (Radar 2969954)
 216  * AOL is adding a circular route ("10.0.1.1/32 10.0.1.1") when establishing its ppp tunnel
 217  * to the AP BaseStation by removing the default gateway and replacing it with their tunnel entry point.
 218  * There is no apparent reason to add this route as there is a valid 10.0.1.1/24 route to the BS.
 219  * That circular route was ignored on previous version of MacOS X because of a routing bug
 220  * corrected with the merge to FreeBSD4.4 (a route generated from an RTF_CLONING route had the RTF_WASCLONED
 221  * flag set but did not have a reference to the parent route) and that entry was left in the RT. This workaround is
 222  * made in order to provide binary compatibility with AOL.
 223  * If we catch a process adding a circular route with a /32 from the routing socket, we error it out instead of
 224  * confusing the routing table with a wrong route to the previous default gateway
 225  * If for some reason a circular route is needed, turn this sysctl (net.inet.ip.check_route_selfref) to zero.
 226  */
 227 int check_routeselfref = 1;
 228 SYSCTL_INT(_net_inet_ip, OID_AUTO, check_route_selfref, CTLFLAG_RW,
 229     &check_routeselfref , 0, "");
 230 #endif
 231
 232 __private_extern__ int use_routegenid = 1;
 233 SYSCTL_INT(_net_inet_ip, OID_AUTO, use_route_genid, CTLFLAG_RW,
 234     &use_routegenid , 0, "");
 235
 236 /*
 237  * On last reference drop, mark the route as belong to us so that it can be
 238  * timed out.
 239  */
 240 static void
 241 in_clsroute(struct radix_node *rn, __unused struct radix_node_head *head)
 242 {
 243         struct rtentry *rt = (struct rtentry *)rn;
 244
 245         if (!(rt->rt_flags & RTF_UP))
 246                 return;         /* prophylactic measures */
 247
 248         if ((rt->rt_flags & (RTF_LLINFO | RTF_HOST)) != RTF_HOST)
 249                 return;
 250
 251         if ((rt->rt_flags & (RTF_WASCLONED | RTPRF_OURS)) != RTF_WASCLONED)
 252                 return;
 253
 254         /*
 255          * Delete the route immediately if RTF_DELCLONE is set or
 256          * if route caching is disabled (rtq_reallyold set to 0).
 257          * Otherwise, let it expire and be deleted by in_rtqkill().
 258          */
 259         if ((rt->rt_flags & RTF_DELCLONE) || rtq_reallyold == 0) {
 260                 /*
 261                  * Delete the route from the radix tree but since we are
 262                  * called when the route's reference count is 0, don't
 263                  * deallocate it until we return from this routine by
 264                  * telling rtrequest that we're interested in it.
 265                  */
 266                 if (rtrequest_locked(RTM_DELETE, (struct sockaddr *)rt_key(rt),
 267                     rt->rt_gateway, rt_mask(rt), rt->rt_flags, &rt) == 0) {
 268                         /* Now let the caller free it */
 269                         rtunref(rt);
 270                 }
 271         } else {
 272                 struct timeval timenow;
 273
 274                 getmicrotime(&timenow);
 275                 rt->rt_flags |= RTPRF_OURS;
 276                 rt->rt_rmx.rmx_expire = timenow.tv_sec + rtq_reallyold;
 277         }
 278 }
 279
 280 struct rtqk_arg {
 281         struct radix_node_head *rnh;
 282         int draining;
 283         int killed;
 284         int found;
 285         int updating;
 286         time_t nextstop;
 287 };
 288
 289 /*
 290  * Get rid of old routes.  When draining, this deletes everything, even when
 291  * the timeout is not expired yet.  When updating, this makes sure that
 292  * nothing has a timeout longer than the current value of rtq_reallyold.
 293  */
 294 static int
 295 in_rtqkill(struct radix_node *rn, void *rock)
 296 {
 297         struct rtqk_arg *ap = rock;
 298         struct rtentry *rt = (struct rtentry *)rn;
 299         int err;
 300         struct timeval timenow;
 301
 302         getmicrotime(&timenow);
 303         lck_mtx_assert(rt_mtx, LCK_MTX_ASSERT_OWNED);
 304
 305         if (rt->rt_flags & RTPRF_OURS) {
 306                 ap->found++;
 307
 308                 if (ap->draining || rt->rt_rmx.rmx_expire <= timenow.tv_sec) {
 309                         if (rt->rt_refcnt > 0)
 310                                 panic("rtqkill route really not free");
 311
 312                         err = rtrequest_locked(RTM_DELETE,
 313                                         (struct sockaddr *)rt_key(rt),
 314                                         rt->rt_gateway, rt_mask(rt),
 315                                         rt->rt_flags, 0);
 316                         if (err) {
 317                                 log(LOG_WARNING, "in_rtqkill: error %d\n", err);
 318                         } else {
 319                                 ap->killed++;
 320                         }
 321                 } else {
 322                         if (ap->updating
 323                            && (rt->rt_rmx.rmx_expire - timenow.tv_sec
 324                                > rtq_reallyold)) {
 325                                 rt->rt_rmx.rmx_expire = timenow.tv_sec
 326                                         + rtq_reallyold;
 327                         }
 328                         ap->nextstop = lmin(ap->nextstop,
 329                                             rt->rt_rmx.rmx_expire);
 330                 }
 331         }
 332
 333         return 0;
 334 }
 335
 336 static void
 337 in_rtqtimo_funnel(void *rock)
 338 {
 339         in_rtqtimo(rock);
 340
 341 }
 342 #define RTQ_TIMEOUT     60*10   /* run no less than once every ten minutes */
 343 static int rtq_timeout = RTQ_TIMEOUT;
 344
 345 static void
 346 in_rtqtimo(void *rock)
 347 {
 348         struct radix_node_head *rnh = rock;
 349         struct rtqk_arg arg;
 350         struct timeval atv;
 351         static time_t last_adjusted_timeout = 0;
 352         struct timeval timenow;
 353
 354         lck_mtx_lock(rt_mtx);
 355         /* Get the timestamp after we acquire the lock for better accuracy */
 356         getmicrotime(&timenow);
 357
 358         arg.found = arg.killed = 0;
 359         arg.rnh = rnh;
 360         arg.nextstop = timenow.tv_sec + rtq_timeout;
 361         arg.draining = arg.updating = 0;
 362         rnh->rnh_walktree(rnh, in_rtqkill, &arg);
 363
 364         /*
 365          * Attempt to be somewhat dynamic about this:
 366          * If there are ``too many'' routes sitting around taking up space,
 367          * then crank down the timeout, and see if we can't make some more
 368          * go away.  However, we make sure that we will never adjust more
 369          * than once in rtq_timeout seconds, to keep from cranking down too
 370          * hard.
 371          */
 372         if((arg.found - arg.killed > rtq_toomany)
 373            && (timenow.tv_sec - last_adjusted_timeout >= rtq_timeout)
 374            && rtq_reallyold > rtq_minreallyold) {
 375                 rtq_reallyold = 2*rtq_reallyold / 3;
 376                 if(rtq_reallyold < rtq_minreallyold) {
 377                         rtq_reallyold = rtq_minreallyold;
 378                 }
 379
 380                 last_adjusted_timeout = timenow.tv_sec;
 381 #if DIAGNOSTIC
 382                 log(LOG_DEBUG, "in_rtqtimo: adjusted rtq_reallyold to %d\n",
 383                     rtq_reallyold);
 384 #endif
 385                 arg.found = arg.killed = 0;
 386                 arg.updating = 1;
 387                 rnh->rnh_walktree(rnh, in_rtqkill, &arg);
 388         }
 389
 390         atv.tv_usec = 0;
 391         atv.tv_sec = arg.nextstop - timenow.tv_sec;
 392         lck_mtx_unlock(rt_mtx);
 393         timeout(in_rtqtimo_funnel, rock, tvtohz(&atv));
 394 }
 395
 396 void
 397 in_rtqdrain(void)
 398 {
 399         struct radix_node_head *rnh = rt_tables[AF_INET];
 400         struct rtqk_arg arg;
 401         arg.found = arg.killed = 0;
 402         arg.rnh = rnh;
 403         arg.nextstop = 0;
 404         arg.draining = 1;
 405         arg.updating = 0;
 406         lck_mtx_lock(rt_mtx);
 407         rnh->rnh_walktree(rnh, in_rtqkill, &arg);
 408         lck_mtx_unlock(rt_mtx);
 409 }
 410
 411 /*
 412  * Initialize our routing tree.
 413  */
 414 int
 415 in_inithead(void **head, int off)
 416 {
 417         struct radix_node_head *rnh;
 418
 419 #ifdef __APPLE__
 420         if (*head)
 421                 return 1;
 422 #endif
 423
 424         if(!rn_inithead(head, off))
 425                 return 0;
 426
 427         if(head != (void **)&rt_tables[AF_INET]) /* BOGUS! */
 428                 return 1;       /* only do this for the real routing table */
 429
 430         rnh = *head;
 431         rnh->rnh_addaddr = in_addroute;
 432         rnh->rnh_matchaddr = in_matroute;
 433         rnh->rnh_close = in_clsroute;
 434         in_rtqtimo(rnh);        /* kick off timeout first time */
 435         return 1;
 436 }
 437
 438 \f
 439 /*
 440  * This zaps old routes when the interface goes down or interface
 441  * address is deleted.  In the latter case, it deletes static routes
 442  * that point to this address.  If we don't do this, we may end up
 443  * using the old address in the future.  The ones we always want to
 444  * get rid of are things like ARP entries, since the user might down
 445  * the interface, walk over to a completely different network, and
 446  * plug back in.
 447  */
 448 struct in_ifadown_arg {
 449         struct radix_node_head *rnh;
 450         struct ifaddr *ifa;
 451         int del;
 452 };
 453
 454 static int
 455 in_ifadownkill(struct radix_node *rn, void *xap)
 456 {
 457         struct in_ifadown_arg *ap = xap;
 458         struct rtentry *rt = (struct rtentry *)rn;
 459         int err;
 460
 461         if (rt->rt_ifa == ap->ifa &&
 462             (ap->del || !(rt->rt_flags & RTF_STATIC))) {
 463                 /*
 464                  * We need to disable the automatic prune that happens
 465                  * in this case in rtrequest() because it will blow
 466                  * away the pointers that rn_walktree() needs in order
 467                  * continue our descent.  We will end up deleting all
 468                  * the routes that rtrequest() would have in any case,
 469                  * so that behavior is not needed there.
 470                  */
 471                 rt->rt_flags &= ~(RTF_CLONING | RTF_PRCLONING);
 472                 err = rtrequest_locked(RTM_DELETE, (struct sockaddr *)rt_key(rt),
 473                                 rt->rt_gateway, rt_mask(rt), rt->rt_flags, 0);
 474                 if (err) {
 475                         log(LOG_WARNING, "in_ifadownkill: error %d\n", err);
 476                 }
 477         }
 478         return 0;
 479 }
 480
 481 int
 482 in_ifadown(struct ifaddr *ifa, int delete)
 483 {
 484         struct in_ifadown_arg arg;
 485         struct radix_node_head *rnh;
 486
 487         lck_mtx_assert(rt_mtx, LCK_MTX_ASSERT_OWNED);
 488
 489         if (ifa->ifa_addr->sa_family != AF_INET)
 490                 return 1;
 491
 492         /* trigger route cache reevaluation */
 493         if (use_routegenid)
 494                 route_generation++;
 495
 496         arg.rnh = rnh = rt_tables[AF_INET];
 497         arg.ifa = ifa;
 498         arg.del = delete;
 499         rnh->rnh_walktree(rnh, in_ifadownkill, &arg);
 500         ifa->ifa_flags &= ~IFA_ROUTE;
 501         return 0;
 502 }