sbin/routed/table.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-3-Clause
   3  *
   4  * Copyright (c) 1983, 1988, 1993
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  * 1. Redistributions of source code must retain the above copyright
  11  *    notice, this list of conditions and the following disclaimer.
  12  * 2. Redistributions in binary form must reproduce the above copyright
  13  *    notice, this list of conditions and the following disclaimer in the
  14  *    documentation and/or other materials provided with the distribution.
  15  * 3. Neither the name of the University nor the names of its contributors
  16  *    may be used to endorse or promote products derived from this software
  17  *    without specific prior written permission.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  20  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  22  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  23  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  25  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  26  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  27  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  28  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  29  * SUCH DAMAGE.
  30  *
  31  * $FreeBSD$
  32  */
  33
  34 #include "defs.h"
  35
  36 #ifdef __NetBSD__
  37 __RCSID("$NetBSD$");
  38 #elif defined(__FreeBSD__)
  39 __RCSID("$FreeBSD$");
  40 #else
  41 __RCSID("$Revision: 2.27 $");
  42 #ident "$Revision: 2.27 $"
  43 #endif
  44
  45 static struct rt_spare *rts_better(struct rt_entry *);
  46 static struct rt_spare rts_empty = {0,0,0,HOPCNT_INFINITY,0,0,0};
  47 static void  set_need_flash(void);
  48 #ifdef _HAVE_SIN_LEN
  49 static void masktrim(struct sockaddr_in *ap);
  50 #else
  51 static void masktrim(struct sockaddr_in_new *ap);
  52 #endif
  53 static void rtbad(struct rt_entry *);
  54
  55
  56 struct radix_node_head *rhead;          /* root of the radix tree */
  57
  58 int     need_flash = 1;                 /* flash update needed
  59                                          * start =1 to suppress the 1st
  60                                          */
  61
  62 struct timeval age_timer;               /* next check of old routes */
  63 struct timeval need_kern = {            /* need to update kernel table */
  64         EPOCH+MIN_WAITTIME-1, 0
  65 };
  66
  67 int     stopint;
  68
  69 int     total_routes;
  70
  71 /* zap any old routes through this gateway */
  72 static naddr age_bad_gate;
  73
  74
  75 /* It is desirable to "aggregate" routes, to combine differing routes of
  76  * the same metric and next hop into a common route with a smaller netmask
  77  * or to suppress redundant routes, routes that add no information to
  78  * routes with smaller netmasks.
  79  *
  80  * A route is redundant if and only if any and all routes with smaller
  81  * but matching netmasks and nets are the same.  Since routes are
  82  * kept sorted in the radix tree, redundant routes always come second.
  83  *
  84  * There are two kinds of aggregations.  First, two routes of the same bit
  85  * mask and differing only in the least significant bit of the network
  86  * number can be combined into a single route with a coarser mask.
  87  *
  88  * Second, a route can be suppressed in favor of another route with a more
  89  * coarse mask provided no incompatible routes with intermediate masks
  90  * are present.  The second kind of aggregation involves suppressing routes.
  91  * A route must not be suppressed if an incompatible route exists with
  92  * an intermediate mask, since the suppressed route would be covered
  93  * by the intermediate.
  94  *
  95  * This code relies on the radix tree walk encountering routes
  96  * sorted first by address, with the smallest address first.
  97  */
  98
  99 static struct ag_info ag_slots[NUM_AG_SLOTS], *ag_avail, *ag_corsest, *ag_finest;
 100
 101 /* #define DEBUG_AG */
 102 #ifdef DEBUG_AG
 103 #define CHECK_AG() {int acnt = 0; struct ag_info *cag;          \
 104         for (cag = ag_avail; cag != NULL; cag = cag->ag_fine)   \
 105                 acnt++;                                         \
 106         for (cag = ag_corsest; cag != NULL; cag = cag->ag_fine) \
 107                 acnt++;                                         \
 108         if (acnt != NUM_AG_SLOTS) {                             \
 109                 (void)fflush(stderr);                           \
 110                 abort();                                        \
 111         }                                                       \
 112 }
 113 #else
 114 #define CHECK_AG()
 115 #endif
 116
 117
 118 /* Output the contents of an aggregation table slot.
 119  *      This function must always be immediately followed with the deletion
 120  *      of the target slot.
 121  */
 122 static void
 123 ag_out(struct ag_info *ag,
 124          void (*out)(struct ag_info *))
 125 {
 126         struct ag_info *ag_cors;
 127         naddr bit;
 128
 129
 130         /* Forget it if this route should not be output for split-horizon. */
 131         if (ag->ag_state & AGS_SPLIT_HZ)
 132                 return;
 133
 134         /* If we output both the even and odd twins, then the immediate parent,
 135          * if it is present, is redundant, unless the parent manages to
 136          * aggregate into something coarser.
 137          * On successive calls, this code detects the even and odd twins,
 138          * and marks the parent.
 139          *
 140          * Note that the order in which the radix tree code emits routes
 141          * ensures that the twins are seen before the parent is emitted.
 142          */
 143         ag_cors = ag->ag_cors;
 144         if (ag_cors != NULL
 145             && ag_cors->ag_mask == ag->ag_mask<<1
 146             && ag_cors->ag_dst_h == (ag->ag_dst_h & ag_cors->ag_mask)) {
 147                 ag_cors->ag_state |= ((ag_cors->ag_dst_h == ag->ag_dst_h)
 148                                       ? AGS_REDUN0
 149                                       : AGS_REDUN1);
 150         }
 151
 152         /* Skip it if this route is itself redundant.
 153          *
 154          * It is ok to change the contents of the slot here, since it is
 155          * always deleted next.
 156          */
 157         if (ag->ag_state & AGS_REDUN0) {
 158                 if (ag->ag_state & AGS_REDUN1)
 159                         return;         /* quit if fully redundant */
 160                 /* make it finer if it is half-redundant */
 161                 bit = (-ag->ag_mask) >> 1;
 162                 ag->ag_dst_h |= bit;
 163                 ag->ag_mask |= bit;
 164
 165         } else if (ag->ag_state & AGS_REDUN1) {
 166                 /* make it finer if it is half-redundant */
 167                 bit = (-ag->ag_mask) >> 1;
 168                 ag->ag_mask |= bit;
 169         }
 170         out(ag);
 171 }
 172
 173
 174 static void
 175 ag_del(struct ag_info *ag)
 176 {
 177         CHECK_AG();
 178
 179         if (ag->ag_cors == NULL)
 180                 ag_corsest = ag->ag_fine;
 181         else
 182                 ag->ag_cors->ag_fine = ag->ag_fine;
 183
 184         if (ag->ag_fine == NULL)
 185                 ag_finest = ag->ag_cors;
 186         else
 187                 ag->ag_fine->ag_cors = ag->ag_cors;
 188
 189         ag->ag_fine = ag_avail;
 190         ag_avail = ag;
 191
 192         CHECK_AG();
 193 }
 194
 195
 196 /* Flush routes waiting for aggregation.
 197  *      This must not suppress a route unless it is known that among all
 198  *      routes with coarser masks that match it, the one with the longest
 199  *      mask is appropriate.  This is ensured by scanning the routes
 200  *      in lexical order, and with the most restrictive mask first
 201  *      among routes to the same destination.
 202  */
 203 void
 204 ag_flush(naddr lim_dst_h,               /* flush routes to here */
 205          naddr lim_mask,                /* matching this mask */
 206          void (*out)(struct ag_info *))
 207 {
 208         struct ag_info *ag, *ag_cors;
 209         naddr dst_h;
 210
 211
 212         for (ag = ag_finest;
 213              ag != NULL && ag->ag_mask >= lim_mask;
 214              ag = ag_cors) {
 215                 ag_cors = ag->ag_cors;
 216
 217                 /* work on only the specified routes */
 218                 dst_h = ag->ag_dst_h;
 219                 if ((dst_h & lim_mask) != lim_dst_h)
 220                         continue;
 221
 222                 if (!(ag->ag_state & AGS_SUPPRESS))
 223                         ag_out(ag, out);
 224
 225                 else for ( ; ; ag_cors = ag_cors->ag_cors) {
 226                         /* Look for a route that can suppress the
 227                          * current route */
 228                         if (ag_cors == NULL) {
 229                                 /* failed, so output it and look for
 230                                  * another route to work on
 231                                  */
 232                                 ag_out(ag, out);
 233                                 break;
 234                         }
 235
 236                         if ((dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h) {
 237                                 /* We found a route with a coarser mask that
 238                                  * aggregates the current target.
 239                                  *
 240                                  * If it has a different next hop, it
 241                                  * cannot replace the target, so output
 242                                  * the target.
 243                                  */
 244                                 if (ag->ag_gate != ag_cors->ag_gate
 245                                     && !(ag->ag_state & AGS_FINE_GATE)
 246                                     && !(ag_cors->ag_state & AGS_CORS_GATE)) {
 247                                         ag_out(ag, out);
 248                                         break;
 249                                 }
 250
 251                                 /* If the coarse route has a good enough
 252                                  * metric, it suppresses the target.
 253                                  * If the suppressed target was redundant,
 254                                  * then mark the suppressor redundant.
 255                                  */
 256                                 if (ag_cors->ag_pref <= ag->ag_pref) {
 257                                     if (AG_IS_REDUN(ag->ag_state)
 258                                         && ag_cors->ag_mask==ag->ag_mask<<1) {
 259                                         if (ag_cors->ag_dst_h == dst_h)
 260                                             ag_cors->ag_state |= AGS_REDUN0;
 261                                         else
 262                                             ag_cors->ag_state |= AGS_REDUN1;
 263                                     }
 264                                     if (ag->ag_tag != ag_cors->ag_tag)
 265                                             ag_cors->ag_tag = 0;
 266                                     if (ag->ag_nhop != ag_cors->ag_nhop)
 267                                             ag_cors->ag_nhop = 0;
 268                                     break;
 269                                 }
 270                         }
 271                 }
 272
 273                 /* That route has either been output or suppressed */
 274                 ag_cors = ag->ag_cors;
 275                 ag_del(ag);
 276         }
 277
 278         CHECK_AG();
 279 }
 280
 281
 282 /* Try to aggregate a route with previous routes.
 283  */
 284 void
 285 ag_check(naddr  dst,
 286          naddr  mask,
 287          naddr  gate,
 288          naddr  nhop,
 289          char   metric,
 290          char   pref,
 291          u_int  new_seqno,
 292          u_short tag,
 293          u_short state,
 294          void (*out)(struct ag_info *)) /* output using this */
 295 {
 296         struct ag_info *ag, *nag, *ag_cors;
 297         naddr xaddr;
 298         int x;
 299
 300         dst = ntohl(dst);
 301
 302         /* Punt non-contiguous subnet masks.
 303          *
 304          * (X & -X) contains a single bit if and only if X is a power of 2.
 305          * (X + (X & -X)) == 0 if and only if X is a power of 2.
 306          */
 307         if ((mask & -mask) + mask != 0) {
 308                 struct ag_info nc_ag;
 309
 310                 nc_ag.ag_dst_h = dst;
 311                 nc_ag.ag_mask = mask;
 312                 nc_ag.ag_gate = gate;
 313                 nc_ag.ag_nhop = nhop;
 314                 nc_ag.ag_metric = metric;
 315                 nc_ag.ag_pref = pref;
 316                 nc_ag.ag_tag = tag;
 317                 nc_ag.ag_state = state;
 318                 nc_ag.ag_seqno = new_seqno;
 319                 out(&nc_ag);
 320                 return;
 321         }
 322
 323         /* Search for the right slot in the aggregation table.
 324          */
 325         ag_cors = NULL;
 326         ag = ag_corsest;
 327         while (ag != NULL) {
 328                 if (ag->ag_mask >= mask)
 329                         break;
 330
 331                 /* Suppress old routes (i.e. combine with compatible routes
 332                  * with coarser masks) as we look for the right slot in the
 333                  * aggregation table for the new route.
 334                  * A route to an address less than the current destination
 335                  * will not be affected by the current route or any route
 336                  * seen hereafter.  That means it is safe to suppress it.
 337                  * This check keeps poor routes (e.g. with large hop counts)
 338                  * from preventing suppression of finer routes.
 339                  */
 340                 if (ag_cors != NULL
 341                     && ag->ag_dst_h < dst
 342                     && (ag->ag_state & AGS_SUPPRESS)
 343                     && ag_cors->ag_pref <= ag->ag_pref
 344                     && (ag->ag_dst_h & ag_cors->ag_mask) == ag_cors->ag_dst_h
 345                     && (ag_cors->ag_gate == ag->ag_gate
 346                         || (ag->ag_state & AGS_FINE_GATE)
 347                         || (ag_cors->ag_state & AGS_CORS_GATE))) {
 348                         /*  If the suppressed target was redundant,
 349                          * then mark the suppressor redundant.
 350                          */
 351                         if (AG_IS_REDUN(ag->ag_state)
 352                             && ag_cors->ag_mask == ag->ag_mask<<1) {
 353                                 if (ag_cors->ag_dst_h == dst)
 354                                         ag_cors->ag_state |= AGS_REDUN0;
 355                                 else
 356                                         ag_cors->ag_state |= AGS_REDUN1;
 357                         }
 358                         if (ag->ag_tag != ag_cors->ag_tag)
 359                                 ag_cors->ag_tag = 0;
 360                         if (ag->ag_nhop != ag_cors->ag_nhop)
 361                                 ag_cors->ag_nhop = 0;
 362                         ag_del(ag);
 363                         CHECK_AG();
 364                 } else {
 365                         ag_cors = ag;
 366                 }
 367                 ag = ag_cors->ag_fine;
 368         }
 369
 370         /* If we find the even/odd twin of the new route, and if the
 371          * masks and so forth are equal, we can aggregate them.
 372          * We can probably promote one of the pair.
 373          *
 374          * Since the routes are encountered in lexical order,
 375          * the new route must be odd.  However, the second or later
 376          * times around this loop, it could be the even twin promoted
 377          * from the even/odd pair of twins of the finer route.
 378          */
 379         while (ag != NULL
 380                && ag->ag_mask == mask
 381                && ((ag->ag_dst_h ^ dst) & (mask<<1)) == 0) {
 382
 383                 /* Here we know the target route and the route in the current
 384                  * slot have the same netmasks and differ by at most the
 385                  * last bit.  They are either for the same destination, or
 386                  * for an even/odd pair of destinations.
 387                  */
 388                 if (ag->ag_dst_h == dst) {
 389                         /* We have two routes to the same destination.
 390                          * Routes are encountered in lexical order, so a
 391                          * route is never promoted until the parent route is
 392                          * already present.  So we know that the new route is
 393                          * a promoted (or aggregated) pair and the route
 394                          * already in the slot is the explicit route.
 395                          *
 396                          * Prefer the best route if their metrics differ,
 397                          * or the aggregated one if not, following a sort
 398                          * of longest-match rule.
 399                          */
 400                         if (pref <= ag->ag_pref) {
 401                                 ag->ag_gate = gate;
 402                                 ag->ag_nhop = nhop;
 403                                 ag->ag_tag = tag;
 404                                 ag->ag_metric = metric;
 405                                 ag->ag_pref = pref;
 406                                 if (ag->ag_seqno < new_seqno)
 407                                         ag->ag_seqno = new_seqno;
 408                                 x = ag->ag_state;
 409                                 ag->ag_state = state;
 410                                 state = x;
 411                         }
 412
 413                         /* Some bits are set if they are set on either route,
 414                          * except when the route is for an interface.
 415                          */
 416                         if (!(ag->ag_state & AGS_IF))
 417                                 ag->ag_state |= (state & (AGS_AGGREGATE_EITHER
 418                                                         | AGS_REDUN0
 419                                                         | AGS_REDUN1));
 420                         return;
 421                 }
 422
 423                 /* If one of the routes can be promoted and the other can
 424                  * be suppressed, it may be possible to combine them or
 425                  * worthwhile to promote one.
 426                  *
 427                  * Any route that can be promoted is always
 428                  * marked to be eligible to be suppressed.
 429                  */
 430                 if (!((state & AGS_AGGREGATE)
 431                       && (ag->ag_state & AGS_SUPPRESS))
 432                     && !((ag->ag_state & AGS_AGGREGATE)
 433                          && (state & AGS_SUPPRESS)))
 434                         break;
 435
 436                 /* A pair of even/odd twin routes can be combined
 437                  * if either is redundant, or if they are via the
 438                  * same gateway and have the same metric.
 439                  */
 440                 if (AG_IS_REDUN(ag->ag_state)
 441                     || AG_IS_REDUN(state)
 442                     || (ag->ag_gate == gate
 443                         && ag->ag_pref == pref
 444                         && (state & ag->ag_state & AGS_AGGREGATE) != 0)) {
 445
 446                         /* We have both the even and odd pairs.
 447                          * Since the routes are encountered in order,
 448                          * the route in the slot must be the even twin.
 449                          *
 450                          * Combine and promote (aggregate) the pair of routes.
 451                          */
 452                         if (new_seqno < ag->ag_seqno)
 453                                 new_seqno = ag->ag_seqno;
 454                         if (!AG_IS_REDUN(state))
 455                                 state &= ~AGS_REDUN1;
 456                         if (AG_IS_REDUN(ag->ag_state))
 457                                 state |= AGS_REDUN0;
 458                         else
 459                                 state &= ~AGS_REDUN0;
 460                         state |= (ag->ag_state & AGS_AGGREGATE_EITHER);
 461                         if (ag->ag_tag != tag)
 462                                 tag = 0;
 463                         if (ag->ag_nhop != nhop)
 464                                 nhop = 0;
 465
 466                         /* Get rid of the even twin that was already
 467                          * in the slot.
 468                          */
 469                         ag_del(ag);
 470
 471                 } else if (ag->ag_pref >= pref
 472                            && (ag->ag_state & AGS_AGGREGATE)) {
 473                         /* If we cannot combine the pair, maybe the route
 474                          * with the worse metric can be promoted.
 475                          *
 476                          * Promote the old, even twin, by giving its slot
 477                          * in the table to the new, odd twin.
 478                          */
 479                         ag->ag_dst_h = dst;
 480
 481                         xaddr = ag->ag_gate;
 482                         ag->ag_gate = gate;
 483                         gate = xaddr;
 484
 485                         xaddr = ag->ag_nhop;
 486                         ag->ag_nhop = nhop;
 487                         nhop = xaddr;
 488
 489                         x = ag->ag_tag;
 490                         ag->ag_tag = tag;
 491                         tag = x;
 492
 493                         /* The promoted route is even-redundant only if the
 494                          * even twin was fully redundant.  It is not
 495                          * odd-redundant because the odd-twin will still be
 496                          * in the table.
 497                          */
 498                         x = ag->ag_state;
 499                         if (!AG_IS_REDUN(x))
 500                                 x &= ~AGS_REDUN0;
 501                         x &= ~AGS_REDUN1;
 502                         ag->ag_state = state;
 503                         state = x;
 504
 505                         x = ag->ag_metric;
 506                         ag->ag_metric = metric;
 507                         metric = x;
 508
 509                         x = ag->ag_pref;
 510                         ag->ag_pref = pref;
 511                         pref = x;
 512
 513                         /* take the newest sequence number */
 514                         if (new_seqno <= ag->ag_seqno)
 515                                 new_seqno = ag->ag_seqno;
 516                         else
 517                                 ag->ag_seqno = new_seqno;
 518
 519                 } else {
 520                         if (!(state & AGS_AGGREGATE))
 521                                 break;  /* cannot promote either twin */
 522
 523                         /* Promote the new, odd twin by shaving its
 524                          * mask and address.
 525                          * The promoted route is odd-redundant only if the
 526                          * odd twin was fully redundant.  It is not
 527                          * even-redundant because the even twin is still in
 528                          * the table.
 529                          */
 530                         if (!AG_IS_REDUN(state))
 531                                 state &= ~AGS_REDUN1;
 532                         state &= ~AGS_REDUN0;
 533                         if (new_seqno < ag->ag_seqno)
 534                                 new_seqno = ag->ag_seqno;
 535                         else
 536                                 ag->ag_seqno = new_seqno;
 537                 }
 538
 539                 mask <<= 1;
 540                 dst &= mask;
 541
 542                 if (ag_cors == NULL) {
 543                         ag = ag_corsest;
 544                         break;
 545                 }
 546                 ag = ag_cors;
 547                 ag_cors = ag->ag_cors;
 548         }
 549
 550         /* When we can no longer promote and combine routes,
 551          * flush the old route in the target slot.  Also flush
 552          * any finer routes that we know will never be aggregated by
 553          * the new route.
 554          *
 555          * In case we moved toward coarser masks,
 556          * get back where we belong
 557          */
 558         if (ag != NULL
 559             && ag->ag_mask < mask) {
 560                 ag_cors = ag;
 561                 ag = ag->ag_fine;
 562         }
 563
 564         /* Empty the target slot
 565          */
 566         if (ag != NULL && ag->ag_mask == mask) {
 567                 ag_flush(ag->ag_dst_h, ag->ag_mask, out);
 568                 ag = (ag_cors == NULL) ? ag_corsest : ag_cors->ag_fine;
 569         }
 570
 571 #ifdef DEBUG_AG
 572         (void)fflush(stderr);
 573         if (ag == NULL && ag_cors != ag_finest)
 574                 abort();
 575         if (ag_cors == NULL && ag != ag_corsest)
 576                 abort();
 577         if (ag != NULL && ag->ag_cors != ag_cors)
 578                 abort();
 579         if (ag_cors != NULL && ag_cors->ag_fine != ag)
 580                 abort();
 581         CHECK_AG();
 582 #endif
 583
 584         /* Save the new route on the end of the table.
 585          */
 586         nag = ag_avail;
 587         ag_avail = nag->ag_fine;
 588
 589         nag->ag_dst_h = dst;
 590         nag->ag_mask = mask;
 591         nag->ag_gate = gate;
 592         nag->ag_nhop = nhop;
 593         nag->ag_metric = metric;
 594         nag->ag_pref = pref;
 595         nag->ag_tag = tag;
 596         nag->ag_state = state;
 597         nag->ag_seqno = new_seqno;
 598
 599         nag->ag_fine = ag;
 600         if (ag != NULL)
 601                 ag->ag_cors = nag;
 602         else
 603                 ag_finest = nag;
 604         nag->ag_cors = ag_cors;
 605         if (ag_cors == NULL)
 606                 ag_corsest = nag;
 607         else
 608                 ag_cors->ag_fine = nag;
 609         CHECK_AG();
 610 }
 611
 612 static const char *
 613 rtm_type_name(u_char type)
 614 {
 615         static const char * const rtm_types[] = {
 616                 "RTM_ADD",
 617                 "RTM_DELETE",
 618                 "RTM_CHANGE",
 619                 "RTM_GET",
 620                 "RTM_LOSING",
 621                 "RTM_REDIRECT",
 622                 "RTM_MISS",
 623                 "RTM_LOCK",
 624                 "RTM_OLDADD",
 625                 "RTM_OLDDEL",
 626                 "RTM_RESOLVE",
 627                 "RTM_NEWADDR",
 628                 "RTM_DELADDR",
 629 #ifdef RTM_OIFINFO
 630                 "RTM_OIFINFO",
 631 #endif
 632                 "RTM_IFINFO",
 633                 "RTM_NEWMADDR",
 634                 "RTM_DELMADDR"
 635         };
 636 #define NEW_RTM_PAT "RTM type %#x"
 637         static char name0[sizeof(NEW_RTM_PAT)+2];
 638
 639
 640         if (type > sizeof(rtm_types)/sizeof(rtm_types[0])
 641             || type == 0) {
 642                 snprintf(name0, sizeof(name0), NEW_RTM_PAT, type);
 643                 return name0;
 644         } else {
 645                 return rtm_types[type-1];
 646         }
 647 #undef NEW_RTM_PAT
 648 }
 649
 650
 651 /* Trim a mask in a sockaddr
 652  *      Produce a length of 0 for an address of 0.
 653  *      Otherwise produce the index of the first zero byte.
 654  */
 655 void
 656 #ifdef _HAVE_SIN_LEN
 657 masktrim(struct sockaddr_in *ap)
 658 #else
 659 masktrim(struct sockaddr_in_new *ap)
 660 #endif
 661 {
 662         char *cp;
 663
 664         if (ap->sin_addr.s_addr == 0) {
 665                 ap->sin_len = 0;
 666                 return;
 667         }
 668         cp = (char *)(&ap->sin_addr.s_addr+1);
 669         while (*--cp == 0)
 670                 continue;
 671         ap->sin_len = cp - (char*)ap + 1;
 672 }
 673
 674
 675 /* Tell the kernel to add, delete or change a route
 676  */
 677 static void
 678 rtioctl(int action,                     /* RTM_DELETE, etc */
 679         naddr dst,
 680         naddr gate,
 681         naddr mask,
 682         int metric,
 683         int flags)
 684 {
 685         struct {
 686                 struct rt_msghdr w_rtm;
 687                 struct sockaddr_in w_dst;
 688                 struct sockaddr_in w_gate;
 689 #ifdef _HAVE_SA_LEN
 690                 struct sockaddr_in w_mask;
 691 #else
 692                 struct sockaddr_in_new w_mask;
 693 #endif
 694         } w;
 695         long cc;
 696 #   define PAT " %-10s %s metric=%d flags=%#x"
 697 #   define ARGS rtm_type_name(action), rtname(dst,mask,gate), metric, flags
 698
 699 again:
 700         memset(&w, 0, sizeof(w));
 701         w.w_rtm.rtm_msglen = sizeof(w);
 702         w.w_rtm.rtm_version = RTM_VERSION;
 703         w.w_rtm.rtm_type = action;
 704         w.w_rtm.rtm_flags = flags;
 705         w.w_rtm.rtm_seq = ++rt_sock_seqno;
 706         w.w_rtm.rtm_addrs = RTA_DST|RTA_GATEWAY;
 707         if (metric != 0 || action == RTM_CHANGE) {
 708                 w.w_rtm.rtm_rmx.rmx_hopcount = metric;
 709                 w.w_rtm.rtm_inits |= RTV_HOPCOUNT;
 710         }
 711         w.w_dst.sin_family = AF_INET;
 712         w.w_dst.sin_addr.s_addr = dst;
 713         w.w_gate.sin_family = AF_INET;
 714         w.w_gate.sin_addr.s_addr = gate;
 715 #ifdef _HAVE_SA_LEN
 716         w.w_dst.sin_len = sizeof(w.w_dst);
 717         w.w_gate.sin_len = sizeof(w.w_gate);
 718 #endif
 719         if (mask == HOST_MASK) {
 720                 w.w_rtm.rtm_flags |= RTF_HOST;
 721                 w.w_rtm.rtm_msglen -= sizeof(w.w_mask);
 722         } else {
 723                 w.w_rtm.rtm_addrs |= RTA_NETMASK;
 724                 w.w_mask.sin_addr.s_addr = htonl(mask);
 725 #ifdef _HAVE_SA_LEN
 726                 masktrim(&w.w_mask);
 727                 if (w.w_mask.sin_len == 0)
 728                         w.w_mask.sin_len = sizeof(long);
 729                 w.w_rtm.rtm_msglen -= (sizeof(w.w_mask) - w.w_mask.sin_len);
 730 #endif
 731         }
 732
 733 #ifndef NO_INSTALL
 734         cc = write(rt_sock, &w, w.w_rtm.rtm_msglen);
 735         if (cc < 0) {
 736                 if (errno == ESRCH
 737                     && (action == RTM_CHANGE || action == RTM_DELETE)) {
 738                         trace_act("route disappeared before" PAT, ARGS);
 739                         if (action == RTM_CHANGE) {
 740                                 action = RTM_ADD;
 741                                 goto again;
 742                         }
 743                         return;
 744                 }
 745                 msglog("write(rt_sock)" PAT ": %s", ARGS, strerror(errno));
 746                 return;
 747         } else if (cc != w.w_rtm.rtm_msglen) {
 748                 msglog("write(rt_sock) wrote %ld instead of %d for" PAT,
 749                        cc, w.w_rtm.rtm_msglen, ARGS);
 750                 return;
 751         }
 752 #endif
 753         if (TRACEKERNEL)
 754                 trace_misc("write kernel" PAT, ARGS);
 755 #undef PAT
 756 #undef ARGS
 757 }
 758
 759
 760 #define KHASH_SIZE 71                   /* should be prime */
 761 #define KHASH(a,m) khash_bins[((a) ^ (m)) % KHASH_SIZE]
 762 static struct khash {
 763         struct khash *k_next;
 764         naddr   k_dst;
 765         naddr   k_mask;
 766         naddr   k_gate;
 767         short   k_metric;
 768         u_short k_state;
 769 #define     KS_NEW      0x001
 770 #define     KS_DELETE   0x002           /* need to delete the route */
 771 #define     KS_ADD      0x004           /* add to the kernel */
 772 #define     KS_CHANGE   0x008           /* tell kernel to change the route */
 773 #define     KS_DEL_ADD  0x010           /* delete & add to change the kernel */
 774 #define     KS_STATIC   0x020           /* Static flag in kernel */
 775 #define     KS_GATEWAY  0x040           /* G flag in kernel */
 776 #define     KS_DYNAMIC  0x080           /* result of redirect */
 777 #define     KS_DELETED  0x100           /* already deleted from kernel */
 778 #define     KS_CHECK    0x200
 779         time_t  k_keep;
 780 #define     K_KEEP_LIM  30
 781         time_t  k_redirect_time;        /* when redirected route 1st seen */
 782 } *khash_bins[KHASH_SIZE];
 783
 784
 785 static struct khash*
 786 kern_find(naddr dst, naddr mask, struct khash ***ppk)
 787 {
 788         struct khash *k, **pk;
 789
 790         for (pk = &KHASH(dst,mask); (k = *pk) != NULL; pk = &k->k_next) {
 791                 if (k->k_dst == dst && k->k_mask == mask)
 792                         break;
 793         }
 794         if (ppk != NULL)
 795                 *ppk = pk;
 796         return k;
 797 }
 798
 799
 800 static struct khash*
 801 kern_add(naddr dst, naddr mask)
 802 {
 803         struct khash *k, **pk;
 804
 805         k = kern_find(dst, mask, &pk);
 806         if (k != NULL)
 807                 return k;
 808
 809         k = (struct khash *)rtmalloc(sizeof(*k), "kern_add");
 810
 811         memset(k, 0, sizeof(*k));
 812         k->k_dst = dst;
 813         k->k_mask = mask;
 814         k->k_state = KS_NEW;
 815         k->k_keep = now.tv_sec;
 816         *pk = k;
 817
 818         return k;
 819 }
 820
 821
 822 /* If a kernel route has a non-zero metric, check that it is still in the
 823  *      daemon table, and not deleted by interfaces coming and going.
 824  */
 825 static void
 826 kern_check_static(struct khash *k,
 827                   struct interface *ifp)
 828 {
 829         struct rt_entry *rt;
 830         struct rt_spare new;
 831
 832         if (k->k_metric == 0)
 833                 return;
 834
 835         memset(&new, 0, sizeof(new));
 836         new.rts_ifp = ifp;
 837         new.rts_gate = k->k_gate;
 838         new.rts_router = (ifp != NULL) ? ifp->int_addr : loopaddr;
 839         new.rts_metric = k->k_metric;
 840         new.rts_time = now.tv_sec;
 841
 842         rt = rtget(k->k_dst, k->k_mask);
 843         if (rt != NULL) {
 844                 if (!(rt->rt_state & RS_STATIC))
 845                         rtchange(rt, rt->rt_state | RS_STATIC, &new, 0);
 846         } else {
 847                 rtadd(k->k_dst, k->k_mask, RS_STATIC, &new);
 848         }
 849 }
 850
 851
 852 /* operate on a kernel entry
 853  */
 854 static void
 855 kern_ioctl(struct khash *k,
 856            int action,                  /* RTM_DELETE, etc */
 857            int flags)
 858
 859 {
 860         switch (action) {
 861         case RTM_DELETE:
 862                 k->k_state &= ~KS_DYNAMIC;
 863                 if (k->k_state & KS_DELETED)
 864                         return;
 865                 k->k_state |= KS_DELETED;
 866                 break;
 867         case RTM_ADD:
 868                 k->k_state &= ~KS_DELETED;
 869                 break;
 870         case RTM_CHANGE:
 871                 if (k->k_state & KS_DELETED) {
 872                         action = RTM_ADD;
 873                         k->k_state &= ~KS_DELETED;
 874                 }
 875                 break;
 876         }
 877
 878         rtioctl(action, k->k_dst, k->k_gate, k->k_mask, k->k_metric, flags);
 879 }
 880
 881
 882 /* add a route the kernel told us
 883  */
 884 static void
 885 rtm_add(struct rt_msghdr *rtm,
 886         struct rt_addrinfo *info,
 887         time_t keep)
 888 {
 889         struct khash *k;
 890         struct interface *ifp;
 891         naddr mask;
 892
 893
 894         if (rtm->rtm_flags & RTF_HOST) {
 895                 mask = HOST_MASK;
 896         } else if (INFO_MASK(info) != 0) {
 897                 mask = ntohl(S_ADDR(INFO_MASK(info)));
 898         } else {
 899                 msglog("ignore %s without mask", rtm_type_name(rtm->rtm_type));
 900                 return;
 901         }
 902
 903         k = kern_add(S_ADDR(INFO_DST(info)), mask);
 904         if (k->k_state & KS_NEW)
 905                 k->k_keep = now.tv_sec+keep;
 906         if (INFO_GATE(info) == 0) {
 907                 trace_act("note %s without gateway",
 908                           rtm_type_name(rtm->rtm_type));
 909                 k->k_metric = HOPCNT_INFINITY;
 910         } else if (INFO_GATE(info)->sa_family != AF_INET) {
 911                 trace_act("note %s with gateway AF=%d",
 912                           rtm_type_name(rtm->rtm_type),
 913                           INFO_GATE(info)->sa_family);
 914                 k->k_metric = HOPCNT_INFINITY;
 915         } else {
 916                 k->k_gate = S_ADDR(INFO_GATE(info));
 917                 k->k_metric = rtm->rtm_rmx.rmx_hopcount;
 918                 if (k->k_metric < 0)
 919                         k->k_metric = 0;
 920                 else if (k->k_metric > HOPCNT_INFINITY-1)
 921                         k->k_metric = HOPCNT_INFINITY-1;
 922         }
 923         k->k_state &= ~(KS_DELETE | KS_ADD | KS_CHANGE | KS_DEL_ADD
 924                         | KS_DELETED | KS_GATEWAY | KS_STATIC
 925                         | KS_NEW | KS_CHECK);
 926         if (rtm->rtm_flags & RTF_GATEWAY)
 927                 k->k_state |= KS_GATEWAY;
 928         if (rtm->rtm_flags & RTF_STATIC)
 929                 k->k_state |= KS_STATIC;
 930
 931         if (0 != (rtm->rtm_flags & (RTF_DYNAMIC | RTF_MODIFIED))) {
 932                 if (INFO_AUTHOR(info) != 0
 933                     && INFO_AUTHOR(info)->sa_family == AF_INET)
 934                         ifp = iflookup(S_ADDR(INFO_AUTHOR(info)));
 935                 else
 936                         ifp = NULL;
 937                 if (supplier
 938                     && (ifp == NULL || !(ifp->int_state & IS_REDIRECT_OK))) {
 939                         /* Routers are not supposed to listen to redirects,
 940                          * so delete it if it came via an unknown interface
 941                          * or the interface does not have special permission.
 942                          */
 943                         k->k_state &= ~KS_DYNAMIC;
 944                         k->k_state |= KS_DELETE;
 945                         LIM_SEC(need_kern, 0);
 946                         trace_act("mark for deletion redirected %s --> %s"
 947                                   " via %s",
 948                                   addrname(k->k_dst, k->k_mask, 0),
 949                                   naddr_ntoa(k->k_gate),
 950                                   ifp ? ifp->int_name : "unknown interface");
 951                 } else {
 952                         k->k_state |= KS_DYNAMIC;
 953                         k->k_redirect_time = now.tv_sec;
 954                         trace_act("accept redirected %s --> %s via %s",
 955                                   addrname(k->k_dst, k->k_mask, 0),
 956                                   naddr_ntoa(k->k_gate),
 957                                   ifp ? ifp->int_name : "unknown interface");
 958                 }
 959                 return;
 960         }
 961
 962         /* If it is not a static route, quit until the next comparison
 963          * between the kernel and daemon tables, when it will be deleted.
 964          */
 965         if (!(k->k_state & KS_STATIC)) {
 966                 k->k_state |= KS_DELETE;
 967                 LIM_SEC(need_kern, k->k_keep);
 968                 return;
 969         }
 970
 971         /* Put static routes with real metrics into the daemon table so
 972          * they can be advertised.
 973          *
 974          * Find the interface toward the gateway.
 975          */
 976         ifp = iflookup(k->k_gate);
 977         if (ifp == NULL)
 978                 msglog("static route %s --> %s impossibly lacks ifp",
 979                        addrname(S_ADDR(INFO_DST(info)), mask, 0),
 980                        naddr_ntoa(k->k_gate));
 981
 982         kern_check_static(k, ifp);
 983 }
 984
 985
 986 /* deal with packet loss
 987  */
 988 static void
 989 rtm_lose(struct rt_msghdr *rtm,
 990          struct rt_addrinfo *info)
 991 {
 992         if (INFO_GATE(info) == 0
 993             || INFO_GATE(info)->sa_family != AF_INET) {
 994                 trace_act("ignore %s without gateway",
 995                           rtm_type_name(rtm->rtm_type));
 996                 return;
 997         }
 998
 999         if (rdisc_ok)
1000                 rdisc_age(S_ADDR(INFO_GATE(info)));
1001         age(S_ADDR(INFO_GATE(info)));
1002 }
1003
1004
1005 /* Make the gateway slot of an info structure point to something
1006  * useful.  If it is not already useful, but it specifies an interface,
1007  * then fill in the sockaddr_in provided and point it there.
1008  */
1009 static int
1010 get_info_gate(struct sockaddr **sap,
1011               struct sockaddr_in *rsin)
1012 {
1013         struct sockaddr_dl *sdl = (struct sockaddr_dl *)*sap;
1014         struct interface *ifp;
1015
1016         if (sdl == NULL)
1017                 return 0;
1018         if ((sdl)->sdl_family == AF_INET)
1019                 return 1;
1020         if ((sdl)->sdl_family != AF_LINK)
1021                 return 0;
1022
1023         ifp = ifwithindex(sdl->sdl_index, 1);
1024         if (ifp == NULL)
1025                 return 0;
1026
1027         rsin->sin_addr.s_addr = ifp->int_addr;
1028 #ifdef _HAVE_SA_LEN
1029         rsin->sin_len = sizeof(*rsin);
1030 #endif
1031         rsin->sin_family = AF_INET;
1032         *sap = (struct sockaddr*)rsin;
1033
1034         return 1;
1035 }
1036
1037
1038 /* Clean the kernel table by copying it to the daemon image.
1039  * Eventually the daemon will delete any extra routes.
1040  */
1041 void
1042 flush_kern(void)
1043 {
1044         static char *sysctl_buf;
1045         static size_t sysctl_buf_size = 0;
1046         size_t needed;
1047         int mib[6];
1048         char *next, *lim;
1049         struct rt_msghdr *rtm;
1050         struct sockaddr_in gate_sin;
1051         struct rt_addrinfo info;
1052         int i;
1053         struct khash *k;
1054
1055
1056         for (i = 0; i < KHASH_SIZE; i++) {
1057                 for (k = khash_bins[i]; k != NULL; k = k->k_next) {
1058                         k->k_state |= KS_CHECK;
1059                 }
1060         }
1061
1062         mib[0] = CTL_NET;
1063         mib[1] = PF_ROUTE;
1064         mib[2] = 0;             /* protocol */
1065         mib[3] = 0;             /* wildcard address family */
1066         mib[4] = NET_RT_DUMP;
1067         mib[5] = 0;             /* no flags */
1068         for (;;) {
1069                 if ((needed = sysctl_buf_size) != 0) {
1070                         if (sysctl(mib, 6, sysctl_buf,&needed, 0, 0) >= 0)
1071                                 break;
1072                         if (errno != ENOMEM && errno != EFAULT)
1073                                 BADERR(1,"flush_kern: sysctl(RT_DUMP)");
1074                         free(sysctl_buf);
1075                         needed = 0;
1076                 }
1077                 if (sysctl(mib, 6, 0, &needed, 0, 0) < 0)
1078                         BADERR(1,"flush_kern: sysctl(RT_DUMP) estimate");
1079                 /* Kludge around the habit of some systems, such as
1080                  * BSD/OS 3.1, to not admit how many routes are in the
1081                  * kernel, or at least to be quite wrong.
1082                  */
1083                 needed += 50*(sizeof(*rtm)+5*sizeof(struct sockaddr));
1084                 sysctl_buf = rtmalloc(sysctl_buf_size = needed,
1085                                       "flush_kern sysctl(RT_DUMP)");
1086         }
1087
1088         lim = sysctl_buf + needed;
1089         for (next = sysctl_buf; next < lim; next += rtm->rtm_msglen) {
1090                 rtm = (struct rt_msghdr *)next;
1091                 if (rtm->rtm_msglen == 0) {
1092                         msglog("zero length kernel route at "
1093                                " %#lx in buffer %#lx before %#lx",
1094                                (u_long)rtm, (u_long)sysctl_buf, (u_long)lim);
1095                         break;
1096                 }
1097
1098                 rt_xaddrs(&info,
1099                           (struct sockaddr *)(rtm+1),
1100                           (struct sockaddr *)(next + rtm->rtm_msglen),
1101                           rtm->rtm_addrs);
1102
1103                 if (INFO_DST(&info) == 0
1104                     || INFO_DST(&info)->sa_family != AF_INET)
1105                         continue;
1106
1107 #if defined (RTF_LLINFO)
1108                 /* ignore ARP table entries on systems with a merged route
1109                  * and ARP table.
1110                  */
1111                 if (rtm->rtm_flags & RTF_LLINFO)
1112                         continue;
1113 #endif
1114 #if defined(RTF_WASCLONED) && defined(__FreeBSD__)
1115                 /* ignore cloned routes
1116                  */
1117                 if (rtm->rtm_flags & RTF_WASCLONED)
1118                         continue;
1119 #endif
1120
1121                 /* ignore multicast addresses
1122                  */
1123                 if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info)))))
1124                         continue;
1125
1126                 if (!get_info_gate(&INFO_GATE(&info), &gate_sin))
1127                         continue;
1128
1129                 /* Note static routes and interface routes, and also
1130                  * preload the image of the kernel table so that
1131                  * we can later clean it, as well as avoid making
1132                  * unneeded changes.  Keep the old kernel routes for a
1133                  * few seconds to allow a RIP or router-discovery
1134                  * response to be heard.
1135                  */
1136                 rtm_add(rtm,&info,MIN_WAITTIME);
1137         }
1138
1139         for (i = 0; i < KHASH_SIZE; i++) {
1140                 for (k = khash_bins[i]; k != NULL; k = k->k_next) {
1141                         if (k->k_state & KS_CHECK) {
1142                                 msglog("%s --> %s disappeared from kernel",
1143                                        addrname(k->k_dst, k->k_mask, 0),
1144                                        naddr_ntoa(k->k_gate));
1145                                 del_static(k->k_dst, k->k_mask, k->k_gate, 1);
1146                         }
1147                 }
1148         }
1149 }
1150
1151
1152 /* Listen to announcements from the kernel
1153  */
1154 void
1155 read_rt(void)
1156 {
1157         long cc;
1158         struct interface *ifp;
1159         struct sockaddr_in gate_sin;
1160         naddr mask, gate;
1161         union {
1162                 struct {
1163                         struct rt_msghdr rtm;
1164                         struct sockaddr addrs[RTAX_MAX];
1165                 } r;
1166                 struct if_msghdr ifm;
1167         } m;
1168         char str[100], *strp;
1169         struct rt_addrinfo info;
1170
1171
1172         for (;;) {
1173                 cc = read(rt_sock, &m, sizeof(m));
1174                 if (cc <= 0) {
1175                         if (cc < 0 && errno != EWOULDBLOCK)
1176                                 LOGERR("read(rt_sock)");
1177                         return;
1178                 }
1179
1180                 if (m.r.rtm.rtm_version != RTM_VERSION) {
1181                         msglog("bogus routing message version %d",
1182                                m.r.rtm.rtm_version);
1183                         continue;
1184                 }
1185
1186                 /* Ignore our own results.
1187                  */
1188                 if (m.r.rtm.rtm_type <= RTM_CHANGE
1189                     && m.r.rtm.rtm_pid == mypid) {
1190                         static int complained = 0;
1191                         if (!complained) {
1192                                 msglog("receiving our own change messages");
1193                                 complained = 1;
1194                         }
1195                         continue;
1196                 }
1197
1198                 if (m.r.rtm.rtm_type == RTM_IFINFO
1199                     || m.r.rtm.rtm_type == RTM_NEWADDR
1200                     || m.r.rtm.rtm_type == RTM_DELADDR) {
1201                         ifp = ifwithindex(m.ifm.ifm_index,
1202                                           m.r.rtm.rtm_type != RTM_DELADDR);
1203                         if (ifp == NULL)
1204                                 trace_act("note %s with flags %#x"
1205                                           " for unknown interface index #%d",
1206                                           rtm_type_name(m.r.rtm.rtm_type),
1207                                           m.ifm.ifm_flags,
1208                                           m.ifm.ifm_index);
1209                         else
1210                                 trace_act("note %s with flags %#x for %s",
1211                                           rtm_type_name(m.r.rtm.rtm_type),
1212                                           m.ifm.ifm_flags,
1213                                           ifp->int_name);
1214
1215                         /* After being informed of a change to an interface,
1216                          * check them all now if the check would otherwise
1217                          * be a long time from now, if the interface is
1218                          * not known, or if the interface has been turned
1219                          * off or on.
1220                          */
1221                         if (ifinit_timer.tv_sec-now.tv_sec>=CHECK_BAD_INTERVAL
1222                             || ifp == NULL
1223                             || ((ifp->int_if_flags ^ m.ifm.ifm_flags)
1224                                 & IFF_UP) != 0)
1225                                 ifinit_timer.tv_sec = now.tv_sec;
1226                         continue;
1227                 }
1228 #ifdef RTM_OIFINFO
1229                 if (m.r.rtm.rtm_type == RTM_OIFINFO)
1230                         continue;       /* ignore compat message */
1231 #endif
1232
1233                 strlcpy(str, rtm_type_name(m.r.rtm.rtm_type), sizeof(str));
1234                 strp = &str[strlen(str)];
1235                 if (m.r.rtm.rtm_type <= RTM_CHANGE)
1236                         strp += sprintf(strp," from pid %d",m.r.rtm.rtm_pid);
1237
1238                 /*
1239                  * Only messages that use the struct rt_msghdr format are
1240                  * allowed beyond this point.
1241                  */
1242                 if (m.r.rtm.rtm_type > RTM_RESOLVE) {
1243                         trace_act("ignore %s", str);
1244                         continue;
1245                 }
1246
1247                 rt_xaddrs(&info, m.r.addrs, &m.r.addrs[RTAX_MAX],
1248                           m.r.rtm.rtm_addrs);
1249
1250                 if (INFO_DST(&info) == 0) {
1251                         trace_act("ignore %s without dst", str);
1252                         continue;
1253                 }
1254
1255                 if (INFO_DST(&info)->sa_family != AF_INET) {
1256                         trace_act("ignore %s for AF %d", str,
1257                                   INFO_DST(&info)->sa_family);
1258                         continue;
1259                 }
1260
1261                 mask = ((INFO_MASK(&info) != 0)
1262                         ? ntohl(S_ADDR(INFO_MASK(&info)))
1263                         : (m.r.rtm.rtm_flags & RTF_HOST)
1264                         ? HOST_MASK
1265                         : std_mask(S_ADDR(INFO_DST(&info))));
1266
1267                 strp += sprintf(strp, ": %s",
1268                                 addrname(S_ADDR(INFO_DST(&info)), mask, 0));
1269
1270                 if (IN_MULTICAST(ntohl(S_ADDR(INFO_DST(&info))))) {
1271                         trace_act("ignore multicast %s", str);
1272                         continue;
1273                 }
1274
1275 #if defined(RTF_LLINFO)
1276                 if (m.r.rtm.rtm_flags & RTF_LLINFO) {
1277                         trace_act("ignore ARP %s", str);
1278                         continue;
1279                 }
1280 #endif
1281
1282 #if defined(RTF_WASCLONED) && defined(__FreeBSD__)
1283                 if (m.r.rtm.rtm_flags & RTF_WASCLONED) {
1284                         trace_act("ignore cloned %s", str);
1285                         continue;
1286                 }
1287 #endif
1288
1289                 if (get_info_gate(&INFO_GATE(&info), &gate_sin)) {
1290                         gate = S_ADDR(INFO_GATE(&info));
1291                         strp += sprintf(strp, " --> %s", naddr_ntoa(gate));
1292                 } else {
1293                         gate = 0;
1294                 }
1295
1296                 if (INFO_AUTHOR(&info) != 0)
1297                         strp += sprintf(strp, " by authority of %s",
1298                                         saddr_ntoa(INFO_AUTHOR(&info)));
1299
1300                 switch (m.r.rtm.rtm_type) {
1301                 case RTM_ADD:
1302                 case RTM_CHANGE:
1303                 case RTM_REDIRECT:
1304                         if (m.r.rtm.rtm_errno != 0) {
1305                                 trace_act("ignore %s with \"%s\" error",
1306                                           str, strerror(m.r.rtm.rtm_errno));
1307                         } else {
1308                                 trace_act("%s", str);
1309                                 rtm_add(&m.r.rtm,&info,0);
1310                         }
1311                         break;
1312
1313                 case RTM_DELETE:
1314                         if (m.r.rtm.rtm_errno != 0
1315                             && m.r.rtm.rtm_errno != ESRCH) {
1316                                 trace_act("ignore %s with \"%s\" error",
1317                                           str, strerror(m.r.rtm.rtm_errno));
1318                         } else {
1319                                 trace_act("%s", str);
1320                                 del_static(S_ADDR(INFO_DST(&info)), mask,
1321                                            gate, 1);
1322                         }
1323                         break;
1324
1325                 case RTM_LOSING:
1326                         trace_act("%s", str);
1327                         rtm_lose(&m.r.rtm,&info);
1328                         break;
1329
1330                 default:
1331                         trace_act("ignore %s", str);
1332                         break;
1333                 }
1334         }
1335 }
1336
1337
1338 /* after aggregating, note routes that belong in the kernel
1339  */
1340 static void
1341 kern_out(struct ag_info *ag)
1342 {
1343         struct khash *k;
1344
1345
1346         /* Do not install bad routes if they are not already present.
1347          * This includes routes that had RS_NET_SYN for interfaces that
1348          * recently died.
1349          */
1350         if (ag->ag_metric == HOPCNT_INFINITY) {
1351                 k = kern_find(htonl(ag->ag_dst_h), ag->ag_mask, 0);
1352                 if (k == NULL)
1353                         return;
1354         } else {
1355                 k = kern_add(htonl(ag->ag_dst_h), ag->ag_mask);
1356         }
1357
1358         if (k->k_state & KS_NEW) {
1359                 /* will need to add new entry to the kernel table */
1360                 k->k_state = KS_ADD;
1361                 if (ag->ag_state & AGS_GATEWAY)
1362                         k->k_state |= KS_GATEWAY;
1363                 k->k_gate = ag->ag_gate;
1364                 k->k_metric = ag->ag_metric;
1365                 return;
1366         }
1367
1368         if (k->k_state & KS_STATIC)
1369                 return;
1370
1371         /* modify existing kernel entry if necessary */
1372         if (k->k_gate != ag->ag_gate
1373             || k->k_metric != ag->ag_metric) {
1374                 /* Must delete bad interface routes etc. to change them. */
1375                 if (k->k_metric == HOPCNT_INFINITY)
1376                         k->k_state |= KS_DEL_ADD;
1377                 k->k_gate = ag->ag_gate;
1378                 k->k_metric = ag->ag_metric;
1379                 k->k_state |= KS_CHANGE;
1380         }
1381
1382         /* If the daemon thinks the route should exist, forget
1383          * about any redirections.
1384          * If the daemon thinks the route should exist, eventually
1385          * override manual intervention by the operator.
1386          */
1387         if ((k->k_state & (KS_DYNAMIC | KS_DELETED)) != 0) {
1388                 k->k_state &= ~KS_DYNAMIC;
1389                 k->k_state |= (KS_ADD | KS_DEL_ADD);
1390         }
1391
1392         if ((k->k_state & KS_GATEWAY)
1393             && !(ag->ag_state & AGS_GATEWAY)) {
1394                 k->k_state &= ~KS_GATEWAY;
1395                 k->k_state |= (KS_ADD | KS_DEL_ADD);
1396         } else if (!(k->k_state & KS_GATEWAY)
1397                    && (ag->ag_state & AGS_GATEWAY)) {
1398                 k->k_state |= KS_GATEWAY;
1399                 k->k_state |= (KS_ADD | KS_DEL_ADD);
1400         }
1401
1402         /* Deleting-and-adding is necessary to change aspects of a route.
1403          * Just delete instead of deleting and then adding a bad route.
1404          * Otherwise, we want to keep the route in the kernel.
1405          */
1406         if (k->k_metric == HOPCNT_INFINITY
1407             && (k->k_state & KS_DEL_ADD))
1408                 k->k_state |= KS_DELETE;
1409         else
1410                 k->k_state &= ~KS_DELETE;
1411 #undef RT
1412 }
1413
1414
1415 /* ARGSUSED */
1416 static int
1417 walk_kern(struct radix_node *rn,
1418           struct walkarg *argp UNUSED)
1419 {
1420 #define RT ((struct rt_entry *)rn)
1421         char metric, pref;
1422         u_int ags = 0;
1423
1424
1425         /* Do not install synthetic routes */
1426         if (RT->rt_state & RS_NET_SYN)
1427                 return 0;
1428
1429         if (!(RT->rt_state & RS_IF)) {
1430                 /* This is an ordinary route, not for an interface.
1431                  */
1432
1433                 /* aggregate, ordinary good routes without regard to
1434                  * their metric
1435                  */
1436                 pref = 1;
1437                 ags |= (AGS_GATEWAY | AGS_SUPPRESS | AGS_AGGREGATE);
1438
1439                 /* Do not install host routes directly to hosts, to avoid
1440                  * interfering with ARP entries in the kernel table.
1441                  */
1442                 if (RT_ISHOST(RT)
1443                     && ntohl(RT->rt_dst) == RT->rt_gate)
1444                         return 0;
1445
1446         } else {
1447                 /* This is an interface route.
1448                  * Do not install routes for "external" remote interfaces.
1449                  */
1450                 if (RT->rt_ifp != 0 && (RT->rt_ifp->int_state & IS_EXTERNAL))
1451                         return 0;
1452
1453                 /* Interfaces should override received routes.
1454                  */
1455                 pref = 0;
1456                 ags |= (AGS_IF | AGS_CORS_GATE);
1457
1458                 /* If it is not an interface, or an alias for an interface,
1459                  * it must be a "gateway."
1460                  *
1461                  * If it is a "remote" interface, it is also a "gateway" to
1462                  * the kernel if is not an alias.
1463                  */
1464                 if (RT->rt_ifp == 0
1465                     || (RT->rt_ifp->int_state & IS_REMOTE))
1466                         ags |= (AGS_GATEWAY | AGS_SUPPRESS | AGS_AGGREGATE);
1467         }
1468
1469         /* If RIP is off and IRDP is on, let the route to the discovered
1470          * route suppress any RIP routes.  Eventually the RIP routes
1471          * will time-out and be deleted.  This reaches the steady-state
1472          * quicker.
1473          */
1474         if ((RT->rt_state & RS_RDISC) && rip_sock < 0)
1475                 ags |= AGS_CORS_GATE;
1476
1477         metric = RT->rt_metric;
1478         if (metric == HOPCNT_INFINITY) {
1479                 /* if the route is dead, so try hard to aggregate. */
1480                 pref = HOPCNT_INFINITY;
1481                 ags |= (AGS_FINE_GATE | AGS_SUPPRESS);
1482                 ags &= ~(AGS_IF | AGS_CORS_GATE);
1483         }
1484
1485         ag_check(RT->rt_dst, RT->rt_mask, RT->rt_gate, 0,
1486                  metric,pref, 0, 0, ags, kern_out);
1487         return 0;
1488 #undef RT
1489 }
1490
1491
1492 /* Update the kernel table to match the daemon table.
1493  */
1494 static void
1495 fix_kern(void)
1496 {
1497         int i;
1498         struct khash *k, **pk;
1499
1500
1501         need_kern = age_timer;
1502
1503         /* Walk daemon table, updating the copy of the kernel table.
1504          */
1505         (void)rn_walktree(rhead, walk_kern, 0);
1506         ag_flush(0,0,kern_out);
1507
1508         for (i = 0; i < KHASH_SIZE; i++) {
1509                 for (pk = &khash_bins[i]; (k = *pk) != NULL; ) {
1510                         /* Do not touch static routes */
1511                         if (k->k_state & KS_STATIC) {
1512                                 kern_check_static(k,0);
1513                                 pk = &k->k_next;
1514                                 continue;
1515                         }
1516
1517                         /* check hold on routes deleted by the operator */
1518                         if (k->k_keep > now.tv_sec) {
1519                                 /* ensure we check when the hold is over */
1520                                 LIM_SEC(need_kern, k->k_keep);
1521                                 /* mark for the next cycle */
1522                                 k->k_state |= KS_DELETE;
1523                                 pk = &k->k_next;
1524                                 continue;
1525                         }
1526
1527                         if ((k->k_state & KS_DELETE)
1528                             && !(k->k_state & KS_DYNAMIC)) {
1529                                 kern_ioctl(k, RTM_DELETE, 0);
1530                                 *pk = k->k_next;
1531                                 free(k);
1532                                 continue;
1533                         }
1534
1535                         if (k->k_state & KS_DEL_ADD)
1536                                 kern_ioctl(k, RTM_DELETE, 0);
1537
1538                         if (k->k_state & KS_ADD) {
1539                                 kern_ioctl(k, RTM_ADD,
1540                                            ((0 != (k->k_state & (KS_GATEWAY
1541                                                         | KS_DYNAMIC)))
1542                                             ? RTF_GATEWAY : 0));
1543                         } else if (k->k_state & KS_CHANGE) {
1544                                 kern_ioctl(k,  RTM_CHANGE,
1545                                            ((0 != (k->k_state & (KS_GATEWAY
1546                                                         | KS_DYNAMIC)))
1547                                             ? RTF_GATEWAY : 0));
1548                         }
1549                         k->k_state &= ~(KS_ADD|KS_CHANGE|KS_DEL_ADD);
1550
1551                         /* Mark this route to be deleted in the next cycle.
1552                          * This deletes routes that disappear from the
1553                          * daemon table, since the normal aging code
1554                          * will clear the bit for routes that have not
1555                          * disappeared from the daemon table.
1556                          */
1557                         k->k_state |= KS_DELETE;
1558                         pk = &k->k_next;
1559                 }
1560         }
1561 }
1562
1563
1564 /* Delete a static route in the image of the kernel table.
1565  */
1566 void
1567 del_static(naddr dst,
1568            naddr mask,
1569            naddr gate,
1570            int gone)
1571 {
1572         struct khash *k;
1573         struct rt_entry *rt;
1574
1575         /* Just mark it in the table to be deleted next time the kernel
1576          * table is updated.
1577          * If it has already been deleted, mark it as such, and set its
1578          * keep-timer so that it will not be deleted again for a while.
1579          * This lets the operator delete a route added by the daemon
1580          * and add a replacement.
1581          */
1582         k = kern_find(dst, mask, 0);
1583         if (k != NULL && (gate == 0 || k->k_gate == gate)) {
1584                 k->k_state &= ~(KS_STATIC | KS_DYNAMIC | KS_CHECK);
1585                 k->k_state |= KS_DELETE;
1586                 if (gone) {
1587                         k->k_state |= KS_DELETED;
1588                         k->k_keep = now.tv_sec + K_KEEP_LIM;
1589                 }
1590         }
1591
1592         rt = rtget(dst, mask);
1593         if (rt != NULL && (rt->rt_state & RS_STATIC))
1594                 rtbad(rt);
1595 }
1596
1597
1598 /* Delete all routes generated from ICMP Redirects that use a given gateway,
1599  * as well as old redirected routes.
1600  */
1601 void
1602 del_redirects(naddr bad_gate,
1603               time_t old)
1604 {
1605         int i;
1606         struct khash *k;
1607
1608
1609         for (i = 0; i < KHASH_SIZE; i++) {
1610                 for (k = khash_bins[i]; k != NULL; k = k->k_next) {
1611                         if (!(k->k_state & KS_DYNAMIC)
1612                             || (k->k_state & KS_STATIC))
1613                                 continue;
1614
1615                         if (k->k_gate != bad_gate
1616                             && k->k_redirect_time > old
1617                             && !supplier)
1618                                 continue;
1619
1620                         k->k_state |= KS_DELETE;
1621                         k->k_state &= ~KS_DYNAMIC;
1622                         need_kern.tv_sec = now.tv_sec;
1623                         trace_act("mark redirected %s --> %s for deletion",
1624                                   addrname(k->k_dst, k->k_mask, 0),
1625                                   naddr_ntoa(k->k_gate));
1626                 }
1627         }
1628 }
1629
1630
1631 /* Start the daemon tables.
1632  */
1633 extern int max_keylen;
1634
1635 void
1636 rtinit(void)
1637 {
1638         int i;
1639         struct ag_info *ag;
1640
1641         /* Initialize the radix trees */
1642         max_keylen = sizeof(struct sockaddr_in);
1643         rn_init();
1644         rn_inithead(&rhead, 32);
1645
1646         /* mark all of the slots in the table free */
1647         ag_avail = ag_slots;
1648         for (ag = ag_slots, i = 1; i < NUM_AG_SLOTS; i++) {
1649                 ag->ag_fine = ag+1;
1650                 ag++;
1651         }
1652 }
1653
1654
1655 #ifdef _HAVE_SIN_LEN
1656 static struct sockaddr_in dst_sock = {sizeof(dst_sock), AF_INET, 0, {0}, {0}};
1657 static struct sockaddr_in mask_sock = {sizeof(mask_sock), AF_INET, 0, {0}, {0}};
1658 #else
1659 static struct sockaddr_in_new dst_sock = {_SIN_ADDR_SIZE, AF_INET};
1660 static struct sockaddr_in_new mask_sock = {_SIN_ADDR_SIZE, AF_INET};
1661 #endif
1662
1663
1664 static void
1665 set_need_flash(void)
1666 {
1667         if (!need_flash) {
1668                 need_flash = 1;
1669                 /* Do not send the flash update immediately.  Wait a little
1670                  * while to hear from other routers.
1671                  */
1672                 no_flash.tv_sec = now.tv_sec + MIN_WAITTIME;
1673         }
1674 }
1675
1676
1677 /* Get a particular routing table entry
1678  */
1679 struct rt_entry *
1680 rtget(naddr dst, naddr mask)
1681 {
1682         struct rt_entry *rt;
1683
1684         dst_sock.sin_addr.s_addr = dst;
1685         mask_sock.sin_addr.s_addr = htonl(mask);
1686         masktrim(&mask_sock);
1687         rt = (struct rt_entry *)rhead->rnh_lookup(&dst_sock,&mask_sock,rhead);
1688         if (!rt
1689             || rt->rt_dst != dst
1690             || rt->rt_mask != mask)
1691                 return 0;
1692
1693         return rt;
1694 }
1695
1696
1697 /* Find a route to dst as the kernel would.
1698  */
1699 struct rt_entry *
1700 rtfind(naddr dst)
1701 {
1702         dst_sock.sin_addr.s_addr = dst;
1703         return (struct rt_entry *)rhead->rnh_matchaddr(&dst_sock, rhead);
1704 }
1705
1706
1707 /* add a route to the table
1708  */
1709 void
1710 rtadd(naddr     dst,
1711       naddr     mask,
1712       u_int     state,                  /* rt_state for the entry */
1713       struct    rt_spare *new)
1714 {
1715         struct rt_entry *rt;
1716         naddr smask;
1717         int i;
1718         struct rt_spare *rts;
1719
1720         rt = (struct rt_entry *)rtmalloc(sizeof (*rt), "rtadd");
1721         memset(rt, 0, sizeof(*rt));
1722         for (rts = rt->rt_spares, i = NUM_SPARES; i != 0; i--, rts++)
1723                 rts->rts_metric = HOPCNT_INFINITY;
1724
1725         rt->rt_nodes->rn_key = (caddr_t)&rt->rt_dst_sock;
1726         rt->rt_dst = dst;
1727         rt->rt_dst_sock.sin_family = AF_INET;
1728 #ifdef _HAVE_SIN_LEN
1729         rt->rt_dst_sock.sin_len = dst_sock.sin_len;
1730 #endif
1731         if (mask != HOST_MASK) {
1732                 smask = std_mask(dst);
1733                 if ((smask & ~mask) == 0 && mask > smask)
1734                         state |= RS_SUBNET;
1735         }
1736         mask_sock.sin_addr.s_addr = htonl(mask);
1737         masktrim(&mask_sock);
1738         rt->rt_mask = mask;
1739         rt->rt_state = state;
1740         rt->rt_spares[0] = *new;
1741         rt->rt_time = now.tv_sec;
1742         rt->rt_poison_metric = HOPCNT_INFINITY;
1743         rt->rt_seqno = update_seqno;
1744
1745         if (++total_routes == MAX_ROUTES)
1746                 msglog("have maximum (%d) routes", total_routes);
1747         if (TRACEACTIONS)
1748                 trace_add_del("Add", rt);
1749
1750         need_kern.tv_sec = now.tv_sec;
1751         set_need_flash();
1752
1753         if (0 == rhead->rnh_addaddr(&rt->rt_dst_sock, &mask_sock,
1754                                     rhead, rt->rt_nodes)) {
1755                 msglog("rnh_addaddr() failed for %s mask=%#lx",
1756                        naddr_ntoa(dst), (u_long)mask);
1757                 free(rt);
1758         }
1759 }
1760
1761
1762 /* notice a changed route
1763  */
1764 void
1765 rtchange(struct rt_entry *rt,
1766          u_int  state,                  /* new state bits */
1767          struct rt_spare *new,
1768          char   *label)
1769 {
1770         if (rt->rt_metric != new->rts_metric) {
1771                 /* Fix the kernel immediately if it seems the route
1772                  * has gone bad, since there may be a working route that
1773                  * aggregates this route.
1774                  */
1775                 if (new->rts_metric == HOPCNT_INFINITY) {
1776                         need_kern.tv_sec = now.tv_sec;
1777                         if (new->rts_time >= now.tv_sec - EXPIRE_TIME)
1778                                 new->rts_time = now.tv_sec - EXPIRE_TIME;
1779                 }
1780                 rt->rt_seqno = update_seqno;
1781                 set_need_flash();
1782         }
1783
1784         if (rt->rt_gate != new->rts_gate) {
1785                 need_kern.tv_sec = now.tv_sec;
1786                 rt->rt_seqno = update_seqno;
1787                 set_need_flash();
1788         }
1789
1790         state |= (rt->rt_state & RS_SUBNET);
1791
1792         /* Keep various things from deciding ageless routes are stale.
1793          */
1794         if (!AGE_RT(state, new->rts_ifp))
1795                 new->rts_time = now.tv_sec;
1796
1797         if (TRACEACTIONS)
1798                 trace_change(rt, state, new,
1799                              label ? label : "Chg   ");
1800
1801         rt->rt_state = state;
1802         rt->rt_spares[0] = *new;
1803 }
1804
1805
1806 /* check for a better route among the spares
1807  */
1808 static struct rt_spare *
1809 rts_better(struct rt_entry *rt)
1810 {
1811         struct rt_spare *rts, *rts1;
1812         int i;
1813
1814         /* find the best alternative among the spares */
1815         rts = rt->rt_spares+1;
1816         for (i = NUM_SPARES, rts1 = rts+1; i > 2; i--, rts1++) {
1817                 if (BETTER_LINK(rt,rts1,rts))
1818                         rts = rts1;
1819         }
1820
1821         return rts;
1822 }
1823
1824
1825 /* switch to a backup route
1826  */
1827 void
1828 rtswitch(struct rt_entry *rt,
1829          struct rt_spare *rts)
1830 {
1831         struct rt_spare swap;
1832         char label[10];
1833
1834
1835         /* Do not change permanent routes */
1836         if (0 != (rt->rt_state & (RS_MHOME | RS_STATIC | RS_RDISC
1837                                   | RS_NET_SYN | RS_IF)))
1838                 return;
1839
1840         /* find the best alternative among the spares */
1841         if (rts == NULL)
1842                 rts = rts_better(rt);
1843
1844         /* Do not bother if it is not worthwhile.
1845          */
1846         if (!BETTER_LINK(rt, rts, rt->rt_spares))
1847                 return;
1848
1849         swap = rt->rt_spares[0];
1850         (void)sprintf(label, "Use #%d", (int)(rts - rt->rt_spares));
1851         rtchange(rt, rt->rt_state & ~(RS_NET_SYN | RS_RDISC), rts, label);
1852         if (swap.rts_metric == HOPCNT_INFINITY) {
1853                 *rts = rts_empty;
1854         } else {
1855                 *rts = swap;
1856         }
1857 }
1858
1859
1860 void
1861 rtdelete(struct rt_entry *rt)
1862 {
1863         struct khash *k;
1864
1865
1866         if (TRACEACTIONS)
1867                 trace_add_del("Del", rt);
1868
1869         k = kern_find(rt->rt_dst, rt->rt_mask, 0);
1870         if (k != NULL) {
1871                 k->k_state |= KS_DELETE;
1872                 need_kern.tv_sec = now.tv_sec;
1873         }
1874
1875         dst_sock.sin_addr.s_addr = rt->rt_dst;
1876         mask_sock.sin_addr.s_addr = htonl(rt->rt_mask);
1877         masktrim(&mask_sock);
1878         if (rt != (struct rt_entry *)rhead->rnh_deladdr(&dst_sock, &mask_sock,
1879                                                         rhead)) {
1880                 msglog("rnh_deladdr() failed");
1881         } else {
1882                 free(rt);
1883                 total_routes--;
1884         }
1885 }
1886
1887
1888 void
1889 rts_delete(struct rt_entry *rt,
1890            struct rt_spare *rts)
1891 {
1892         trace_upslot(rt, rts, &rts_empty);
1893         *rts = rts_empty;
1894 }
1895
1896
1897 /* Get rid of a bad route, and try to switch to a replacement.
1898  */
1899 static void
1900 rtbad(struct rt_entry *rt)
1901 {
1902         struct rt_spare new;
1903
1904         /* Poison the route */
1905         new = rt->rt_spares[0];
1906         new.rts_metric = HOPCNT_INFINITY;
1907         rtchange(rt, rt->rt_state & ~(RS_IF | RS_LOCAL | RS_STATIC), &new, 0);
1908         rtswitch(rt, 0);
1909 }
1910
1911
1912 /* Junk a RS_NET_SYN or RS_LOCAL route,
1913  *      unless it is needed by another interface.
1914  */
1915 void
1916 rtbad_sub(struct rt_entry *rt)
1917 {
1918         struct interface *ifp, *ifp1;
1919         struct intnet *intnetp;
1920         u_int state;
1921
1922
1923         ifp1 = NULL;
1924         state = 0;
1925
1926         if (rt->rt_state & RS_LOCAL) {
1927                 /* Is this the route through loopback for the interface?
1928                  * If so, see if it is used by any other interfaces, such
1929                  * as a point-to-point interface with the same local address.
1930                  */
1931                 LIST_FOREACH(ifp, &ifnet, int_list) {
1932                         /* Retain it if another interface needs it.
1933                          */
1934                         if (ifp->int_addr == rt->rt_ifp->int_addr) {
1935                                 state |= RS_LOCAL;
1936                                 ifp1 = ifp;
1937                                 break;
1938                         }
1939                 }
1940
1941         }
1942
1943         if (!(state & RS_LOCAL)) {
1944                 /* Retain RIPv1 logical network route if there is another
1945                  * interface that justifies it.
1946                  */
1947                 if (rt->rt_state & RS_NET_SYN) {
1948                         LIST_FOREACH(ifp, &ifnet, int_list) {
1949                                 if ((ifp->int_state & IS_NEED_NET_SYN)
1950                                     && rt->rt_mask == ifp->int_std_mask
1951                                     && rt->rt_dst == ifp->int_std_addr) {
1952                                         state |= RS_NET_SYN;
1953                                         ifp1 = ifp;
1954                                         break;
1955                                 }
1956                         }
1957                 }
1958
1959                 /* or if there is an authority route that needs it. */
1960                 for (intnetp = intnets;
1961                      intnetp != NULL;
1962                      intnetp = intnetp->intnet_next) {
1963                         if (intnetp->intnet_addr == rt->rt_dst
1964                             && intnetp->intnet_mask == rt->rt_mask) {
1965                                 state |= (RS_NET_SYN | RS_NET_INT);
1966                                 break;
1967                         }
1968                 }
1969         }
1970
1971         if (ifp1 != NULL || (state & RS_NET_SYN)) {
1972                 struct rt_spare new = rt->rt_spares[0];
1973                 new.rts_ifp = ifp1;
1974                 rtchange(rt, ((rt->rt_state & ~(RS_NET_SYN|RS_LOCAL)) | state),
1975                          &new, 0);
1976         } else {
1977                 rtbad(rt);
1978         }
1979 }
1980
1981
1982 /* Called while walking the table looking for sick interfaces
1983  * or after a time change.
1984  */
1985 /* ARGSUSED */
1986 int
1987 walk_bad(struct radix_node *rn,
1988          struct walkarg *argp UNUSED)
1989 {
1990 #define RT ((struct rt_entry *)rn)
1991         struct rt_spare *rts;
1992         int i;
1993
1994
1995         /* fix any spare routes through the interface
1996          */
1997         rts = RT->rt_spares;
1998         for (i = NUM_SPARES; i != 1; i--) {
1999                 rts++;
2000                 if (rts->rts_metric < HOPCNT_INFINITY
2001                     && (rts->rts_ifp == NULL
2002                         || (rts->rts_ifp->int_state & IS_BROKE)))
2003                         rts_delete(RT, rts);
2004         }
2005
2006         /* Deal with the main route
2007          */
2008         /* finished if it has been handled before or if its interface is ok
2009          */
2010         if (RT->rt_ifp == 0 || !(RT->rt_ifp->int_state & IS_BROKE))
2011                 return 0;
2012
2013         /* Bad routes for other than interfaces are easy.
2014          */
2015         if (0 == (RT->rt_state & (RS_IF | RS_NET_SYN | RS_LOCAL))) {
2016                 rtbad(RT);
2017                 return 0;
2018         }
2019
2020         rtbad_sub(RT);
2021         return 0;
2022 #undef RT
2023 }
2024
2025
2026 /* Check the age of an individual route.
2027  */
2028 /* ARGSUSED */
2029 static int
2030 walk_age(struct radix_node *rn,
2031            struct walkarg *argp UNUSED)
2032 {
2033 #define RT ((struct rt_entry *)rn)
2034         struct interface *ifp;
2035         struct rt_spare *rts;
2036         int i;
2037
2038
2039         /* age all of the spare routes, including the primary route
2040          * currently in use
2041          */
2042         rts = RT->rt_spares;
2043         for (i = NUM_SPARES; i != 0; i--, rts++) {
2044
2045                 ifp = rts->rts_ifp;
2046                 if (i == NUM_SPARES) {
2047                         if (!AGE_RT(RT->rt_state, ifp)) {
2048                                 /* Keep various things from deciding ageless
2049                                  * routes are stale
2050                                  */
2051                                 rts->rts_time = now.tv_sec;
2052                                 continue;
2053                         }
2054
2055                         /* forget RIP routes after RIP has been turned off.
2056                          */
2057                         if (rip_sock < 0) {
2058                                 rtdelete(RT);
2059                                 return 0;
2060                         }
2061                 }
2062
2063                 /* age failing routes
2064                  */
2065                 if (age_bad_gate == rts->rts_gate
2066                     && rts->rts_time >= now_stale) {
2067                         rts->rts_time -= SUPPLY_INTERVAL;
2068                 }
2069
2070                 /* trash the spare routes when they go bad */
2071                 if (rts->rts_metric < HOPCNT_INFINITY
2072                     && now_garbage > rts->rts_time
2073                     && i != NUM_SPARES)
2074                         rts_delete(RT, rts);
2075         }
2076
2077
2078         /* finished if the active route is still fresh */
2079         if (now_stale <= RT->rt_time)
2080                 return 0;
2081
2082         /* try to switch to an alternative */
2083         rtswitch(RT, 0);
2084
2085         /* Delete a dead route after it has been publicly mourned. */
2086         if (now_garbage > RT->rt_time) {
2087                 rtdelete(RT);
2088                 return 0;
2089         }
2090
2091         /* Start poisoning a bad route before deleting it. */
2092         if (now.tv_sec - RT->rt_time > EXPIRE_TIME) {
2093                 struct rt_spare new = RT->rt_spares[0];
2094                 new.rts_metric = HOPCNT_INFINITY;
2095                 rtchange(RT, RT->rt_state, &new, 0);
2096         }
2097         return 0;
2098 }
2099
2100
2101 /* Watch for dead routes and interfaces.
2102  */
2103 void
2104 age(naddr bad_gate)
2105 {
2106         struct interface *ifp;
2107         int need_query = 0;
2108
2109         /* If not listening to RIP, there is no need to age the routes in
2110          * the table.
2111          */
2112         age_timer.tv_sec = (now.tv_sec
2113                             + ((rip_sock < 0) ? NEVER : SUPPLY_INTERVAL));
2114
2115         /* Check for dead IS_REMOTE interfaces by timing their
2116          * transmissions.
2117          */
2118         LIST_FOREACH(ifp, &ifnet, int_list) {
2119                 if (!(ifp->int_state & IS_REMOTE))
2120                         continue;
2121
2122                 /* ignore unreachable remote interfaces */
2123                 if (!check_remote(ifp))
2124                         continue;
2125
2126                 /* Restore remote interface that has become reachable
2127                  */
2128                 if (ifp->int_state & IS_BROKE)
2129                         if_ok(ifp, "remote ");
2130
2131                 if (ifp->int_act_time != NEVER
2132                     && now.tv_sec - ifp->int_act_time > EXPIRE_TIME) {
2133                         msglog("remote interface %s to %s timed out after"
2134                                " %ld:%ld",
2135                                ifp->int_name,
2136                                naddr_ntoa(ifp->int_dstaddr),
2137                                (long)(now.tv_sec - ifp->int_act_time)/60,
2138                                (long)(now.tv_sec - ifp->int_act_time)%60);
2139                         if_sick(ifp);
2140                 }
2141
2142                 /* If we have not heard from the other router
2143                  * recently, ask it.
2144                  */
2145                 if (now.tv_sec >= ifp->int_query_time) {
2146                         ifp->int_query_time = NEVER;
2147                         need_query = 1;
2148                 }
2149         }
2150
2151         /* Age routes. */
2152         age_bad_gate = bad_gate;
2153         (void)rn_walktree(rhead, walk_age, 0);
2154
2155         /* delete old redirected routes to keep the kernel table small
2156          * and prevent blackholes
2157          */
2158         del_redirects(bad_gate, now.tv_sec-STALE_TIME);
2159
2160         /* Update the kernel routing table. */
2161         fix_kern();
2162
2163         /* poke reticent remote gateways */
2164         if (need_query)
2165                 rip_query();
2166 }