sbin/routed/rdisc.c

   1 /*
   2  * Copyright (c) 1995
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 4. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  * $FreeBSD$
  30  */
  31
  32 #include "defs.h"
  33 #include <netinet/in_systm.h>
  34 #include <netinet/ip.h>
  35 #include <netinet/ip_icmp.h>
  36
  37 #ifdef __NetBSD__
  38 __RCSID("$NetBSD$");
  39 #elif defined(__FreeBSD__)
  40 __RCSID("$FreeBSD$");
  41 #else
  42 __RCSID("$Revision: 2.27 $");
  43 #ident "$Revision: 2.27 $"
  44 #endif
  45
  46 /* router advertisement ICMP packet */
  47 struct icmp_ad {
  48         u_int8_t    icmp_type;          /* type of message */
  49         u_int8_t    icmp_code;          /* type sub code */
  50         u_int16_t   icmp_cksum;         /* ones complement cksum of struct */
  51         u_int8_t    icmp_ad_num;        /* # of following router addresses */
  52         u_int8_t    icmp_ad_asize;      /* 2--words in each advertisement */
  53         u_int16_t   icmp_ad_life;       /* seconds of validity */
  54         struct icmp_ad_info {
  55             n_long  icmp_ad_addr;
  56             n_long  icmp_ad_pref;
  57         } icmp_ad_info[1];
  58 };
  59
  60 /* router solicitation ICMP packet */
  61 struct icmp_so {
  62         u_int8_t    icmp_type;          /* type of message */
  63         u_int8_t    icmp_code;          /* type sub code */
  64         u_int16_t   icmp_cksum;         /* ones complement cksum of struct */
  65         n_long      icmp_so_rsvd;
  66 };
  67
  68 union ad_u {
  69         struct icmp icmp;
  70         struct icmp_ad ad;
  71         struct icmp_so so;
  72 };
  73
  74
  75 int     rdisc_sock = -1;                /* router-discovery raw socket */
  76 static const struct interface *rdisc_sock_mcast; /* current multicast interface */
  77
  78 struct timeval rdisc_timer;
  79 int rdisc_ok;                           /* using solicited route */
  80
  81
  82 #define MAX_ADS 16                      /* at least one per interface */
  83 struct dr {                             /* accumulated advertisements */
  84     struct interface *dr_ifp;
  85     naddr   dr_gate;                    /* gateway */
  86     time_t  dr_ts;                      /* when received */
  87     time_t  dr_life;                    /* lifetime in host byte order */
  88     n_long  dr_recv_pref;               /* received but biased preference */
  89     n_long  dr_pref;                    /* preference adjusted by metric */
  90 };
  91 static const struct dr *cur_drp;
  92 static struct dr drs[MAX_ADS];
  93
  94 /* convert between signed, balanced around zero,
  95  * and unsigned zero-based preferences */
  96 #define SIGN_PREF(p) ((p) ^ MIN_PreferenceLevel)
  97 #define UNSIGN_PREF(p) SIGN_PREF(p)
  98 /* adjust unsigned preference by interface metric,
  99  * without driving it to infinity */
 100 #define PREF(p, ifp) ((int)(p) <= ((ifp)->int_metric+(ifp)->int_adj_outmetric)\
 101                       ? ((p) != 0 ? 1 : 0)                                  \
 102                       : (p) - ((ifp)->int_metric+(ifp)->int_adj_outmetric))
 103
 104 static void rdisc_sort(void);
 105
 106
 107 /* dump an ICMP Router Discovery Advertisement Message
 108  */
 109 static void
 110 trace_rdisc(const char  *act,
 111             naddr       from,
 112             naddr       to,
 113             struct interface *ifp,
 114             union ad_u  *p,
 115             u_int       len)
 116 {
 117         int i;
 118         n_long *wp, *lim;
 119
 120
 121         if (!TRACEPACKETS || ftrace == 0)
 122                 return;
 123
 124         lastlog();
 125
 126         if (p->icmp.icmp_type == ICMP_ROUTERADVERT) {
 127                 (void)fprintf(ftrace, "%s Router Ad"
 128                               " from %s to %s via %s life=%d\n",
 129                               act, naddr_ntoa(from), naddr_ntoa(to),
 130                               ifp ? ifp->int_name : "?",
 131                               ntohs(p->ad.icmp_ad_life));
 132                 if (!TRACECONTENTS)
 133                         return;
 134
 135                 wp = &p->ad.icmp_ad_info[0].icmp_ad_addr;
 136                 lim = &wp[(len - sizeof(p->ad)) / sizeof(*wp)];
 137                 for (i = 0; i < p->ad.icmp_ad_num && wp <= lim; i++) {
 138                         (void)fprintf(ftrace, "\t%s preference=%d",
 139                                       naddr_ntoa(wp[0]), (int)ntohl(wp[1]));
 140                         wp += p->ad.icmp_ad_asize;
 141                 }
 142                 (void)fputc('\n',ftrace);
 143
 144         } else {
 145                 trace_act("%s Router Solic. from %s to %s via %s value=%#x",
 146                           act, naddr_ntoa(from), naddr_ntoa(to),
 147                           ifp ? ifp->int_name : "?",
 148                           (int)ntohl(p->so.icmp_so_rsvd));
 149         }
 150 }
 151
 152 /* prepare Router Discovery socket.
 153  */
 154 static void
 155 get_rdisc_sock(void)
 156 {
 157         if (rdisc_sock < 0) {
 158                 rdisc_sock = socket(AF_INET, SOCK_RAW, IPPROTO_ICMP);
 159                 if (rdisc_sock < 0)
 160                         BADERR(1,"rdisc_sock = socket()");
 161                 fix_sock(rdisc_sock,"rdisc_sock");
 162                 fix_select();
 163         }
 164 }
 165
 166
 167 /* Pick multicast group for router-discovery socket
 168  */
 169 void
 170 set_rdisc_mg(struct interface *ifp,
 171              int on)                    /* 0=turn it off */
 172 {
 173         struct group_req gr;
 174         struct sockaddr_in *sin;
 175
 176         assert(ifp != NULL);
 177
 178         if (rdisc_sock < 0) {
 179                 /* Create the raw socket so that we can hear at least
 180                  * broadcast router discovery packets.
 181                  */
 182                 if ((ifp->int_state & IS_NO_RDISC) == IS_NO_RDISC
 183                     || !on)
 184                         return;
 185                 get_rdisc_sock();
 186         }
 187
 188         if (!(ifp->int_if_flags & IFF_MULTICAST)) {
 189                 ifp->int_state &= ~(IS_ALL_HOSTS | IS_ALL_ROUTERS);
 190                 return;
 191         }
 192
 193         memset(&gr, 0, sizeof(gr));
 194         gr.gr_interface = ifp->int_index;
 195         sin = (struct sockaddr_in *)&gr.gr_group;
 196         sin->sin_family = AF_INET;
 197 #ifdef _HAVE_SIN_LEN
 198         sin->sin_len = sizeof(struct sockaddr_in);
 199 #endif
 200
 201         if (supplier
 202             || (ifp->int_state & IS_NO_ADV_IN)
 203             || !on) {
 204                 /* stop listening to advertisements
 205                  */
 206                 if (ifp->int_state & IS_ALL_HOSTS) {
 207                         sin->sin_addr.s_addr = htonl(INADDR_ALLHOSTS_GROUP);
 208                         if (setsockopt(rdisc_sock, IPPROTO_IP,
 209                                        MCAST_LEAVE_GROUP,
 210                                        &gr, sizeof(gr)) < 0)
 211                                 LOGERR("MCAST_LEAVE_GROUP ALLHOSTS");
 212                         ifp->int_state &= ~IS_ALL_HOSTS;
 213                 }
 214
 215         } else if (!(ifp->int_state & IS_ALL_HOSTS)) {
 216                 /* start listening to advertisements
 217                  */
 218                 sin->sin_addr.s_addr = htonl(INADDR_ALLHOSTS_GROUP);
 219                 if (setsockopt(rdisc_sock, IPPROTO_IP, MCAST_JOIN_GROUP,
 220                                &gr, sizeof(gr)) < 0) {
 221                         LOGERR("MCAST_JOIN_GROUP ALLHOSTS");
 222                 } else {
 223                         ifp->int_state |= IS_ALL_HOSTS;
 224                 }
 225         }
 226
 227         if (!supplier
 228             || (ifp->int_state & IS_NO_ADV_OUT)
 229             || !on) {
 230                 /* stop listening to solicitations
 231                  */
 232                 if (ifp->int_state & IS_ALL_ROUTERS) {
 233                         sin->sin_addr.s_addr = htonl(INADDR_ALLROUTERS_GROUP);
 234                         if (setsockopt(rdisc_sock, IPPROTO_IP,
 235                                        MCAST_LEAVE_GROUP,
 236                                        &gr, sizeof(gr)) < 0)
 237                                 LOGERR("MCAST_LEAVE_GROUP ALLROUTERS");
 238                         ifp->int_state &= ~IS_ALL_ROUTERS;
 239                 }
 240
 241         } else if (!(ifp->int_state & IS_ALL_ROUTERS)) {
 242                 /* start hearing solicitations
 243                  */
 244                 sin->sin_addr.s_addr = htonl(INADDR_ALLROUTERS_GROUP);
 245                 if (setsockopt(rdisc_sock, IPPROTO_IP, MCAST_JOIN_GROUP,
 246                                &gr, sizeof(gr)) < 0) {
 247                         LOGERR("MCAST_JOIN_GROUP ALLROUTERS");
 248                 } else {
 249                         ifp->int_state |= IS_ALL_ROUTERS;
 250                 }
 251         }
 252 }
 253
 254
 255 /* start supplying routes
 256  */
 257 void
 258 set_supplier(void)
 259 {
 260         struct interface *ifp;
 261         struct dr *drp;
 262
 263         if (supplier_set)
 264                 return;
 265
 266         trace_act("start supplying routes");
 267
 268         /* Forget discovered routes.
 269          */
 270         for (drp = drs; drp < &drs[MAX_ADS]; drp++) {
 271                 drp->dr_recv_pref = 0;
 272                 drp->dr_life = 0;
 273         }
 274         rdisc_age(0);
 275
 276         supplier_set = 1;
 277         supplier = 1;
 278
 279         /* Do not start advertising until we have heard some RIP routes */
 280         LIM_SEC(rdisc_timer, now.tv_sec+MIN_WAITTIME);
 281
 282         /* Switch router discovery multicast groups from soliciting
 283          * to advertising.
 284          */
 285         LIST_FOREACH(ifp, &ifnet, int_list) {
 286                 if (ifp->int_state & IS_BROKE)
 287                         continue;
 288                 ifp->int_rdisc_cnt = 0;
 289                 ifp->int_rdisc_timer.tv_usec = rdisc_timer.tv_usec;
 290                 ifp->int_rdisc_timer.tv_sec = now.tv_sec+MIN_WAITTIME;
 291                 set_rdisc_mg(ifp, 1);
 292         }
 293
 294         /* get rid of any redirects */
 295         del_redirects(0,0);
 296 }
 297
 298
 299 /* age discovered routes and find the best one
 300  */
 301 void
 302 rdisc_age(naddr bad_gate)
 303 {
 304         time_t sec;
 305         struct dr *drp;
 306
 307
 308         /* If only advertising, then do only that. */
 309         if (supplier) {
 310                 /* If switching from client to server, get rid of old
 311                  * default routes.
 312                  */
 313                 if (cur_drp != 0)
 314                         rdisc_sort();
 315                 rdisc_adv();
 316                 return;
 317         }
 318
 319         /* If we are being told about a bad router,
 320          * then age the discovered default route, and if there is
 321          * no alternative, solicit a replacement.
 322          */
 323         if (bad_gate != 0) {
 324                 /* Look for the bad discovered default route.
 325                  * Age it and note its interface.
 326                  */
 327                 for (drp = drs; drp < &drs[MAX_ADS]; drp++) {
 328                         if (drp->dr_ts == 0)
 329                                 continue;
 330
 331                         /* When we find the bad router, then age the route
 332                          * to at most SUPPLY_INTERVAL.
 333                          * This is contrary to RFC 1256, but defends against
 334                          * black holes.
 335                          */
 336                         if (drp->dr_gate == bad_gate) {
 337                                 sec = (now.tv_sec - drp->dr_life
 338                                        + SUPPLY_INTERVAL);
 339                                 if (drp->dr_ts > sec) {
 340                                         trace_act("age 0.0.0.0 --> %s via %s",
 341                                                   naddr_ntoa(drp->dr_gate),
 342                                                   drp->dr_ifp->int_name);
 343                                         drp->dr_ts = sec;
 344                                 }
 345                                 break;
 346                         }
 347                 }
 348         }
 349
 350         rdisc_sol();
 351         rdisc_sort();
 352
 353         /* Delete old redirected routes to keep the kernel table small,
 354          * and to prevent black holes.  Check that the kernel table
 355          * matches the daemon table (i.e. has the default route).
 356          * But only if RIP is not running and we are not dealing with
 357          * a bad gateway, since otherwise age() will be called.
 358          */
 359         if (rip_sock < 0 && bad_gate == 0)
 360                 age(0);
 361 }
 362
 363
 364 /* Zap all routes discovered via an interface that has gone bad
 365  *      This should only be called when !(ifp->int_state & IS_ALIAS)
 366  */
 367 void
 368 if_bad_rdisc(struct interface *ifp)
 369 {
 370         struct dr *drp;
 371
 372         for (drp = drs; drp < &drs[MAX_ADS]; drp++) {
 373                 if (drp->dr_ifp != ifp)
 374                         continue;
 375                 drp->dr_recv_pref = 0;
 376                 drp->dr_ts = 0;
 377                 drp->dr_life = 0;
 378         }
 379
 380         /* make a note to re-solicit, turn RIP on or off, etc. */
 381         rdisc_timer.tv_sec = 0;
 382 }
 383
 384
 385 /* mark an interface ok for router discovering.
 386  */
 387 void
 388 if_ok_rdisc(struct interface *ifp)
 389 {
 390         set_rdisc_mg(ifp, 1);
 391
 392         ifp->int_rdisc_cnt = 0;
 393         ifp->int_rdisc_timer.tv_sec = now.tv_sec + (supplier
 394                                                     ? MIN_WAITTIME
 395                                                     : MAX_SOLICITATION_DELAY);
 396         if (timercmp(&rdisc_timer, &ifp->int_rdisc_timer, >))
 397                 rdisc_timer = ifp->int_rdisc_timer;
 398 }
 399
 400
 401 /* get rid of a dead discovered router
 402  */
 403 static void
 404 del_rdisc(struct dr *drp)
 405 {
 406         struct interface *ifp;
 407         naddr gate;
 408         int i;
 409
 410
 411         del_redirects(gate = drp->dr_gate, 0);
 412         drp->dr_ts = 0;
 413         drp->dr_life = 0;
 414
 415
 416         /* Count the other discovered routes on the interface.
 417          */
 418         i = 0;
 419         ifp = drp->dr_ifp;
 420         for (drp = drs; drp < &drs[MAX_ADS]; drp++) {
 421                 if (drp->dr_ts != 0
 422                     && drp->dr_ifp == ifp)
 423                         i++;
 424         }
 425
 426         /* If that was the last good discovered router on the interface,
 427          * then solicit a new one.
 428          * This is contrary to RFC 1256, but defends against black holes.
 429          */
 430         if (i != 0) {
 431                 trace_act("discovered router %s via %s"
 432                           " is bad--have %d remaining",
 433                           naddr_ntoa(gate), ifp->int_name, i);
 434         } else if (ifp->int_rdisc_cnt >= MAX_SOLICITATIONS) {
 435                 trace_act("last discovered router %s via %s"
 436                           " is bad--re-solicit",
 437                           naddr_ntoa(gate), ifp->int_name);
 438                 ifp->int_rdisc_cnt = 0;
 439                 ifp->int_rdisc_timer.tv_sec = 0;
 440                 rdisc_sol();
 441         } else {
 442                 trace_act("last discovered router %s via %s"
 443                           " is bad--wait to solicit",
 444                           naddr_ntoa(gate), ifp->int_name);
 445         }
 446 }
 447
 448
 449 /* Find the best discovered route,
 450  * and discard stale routers.
 451  */
 452 static void
 453 rdisc_sort(void)
 454 {
 455         struct dr *drp, *new_drp;
 456         struct rt_entry *rt;
 457         struct rt_spare new;
 458         struct interface *ifp;
 459         u_int new_st = 0;
 460         n_long new_pref = 0;
 461
 462
 463         /* Find the best discovered route.
 464          */
 465         new_drp = 0;
 466         for (drp = drs; drp < &drs[MAX_ADS]; drp++) {
 467                 if (drp->dr_ts == 0)
 468                         continue;
 469                 ifp = drp->dr_ifp;
 470
 471                 /* Get rid of expired discovered routers.
 472                  */
 473                 if (drp->dr_ts + drp->dr_life <= now.tv_sec) {
 474                         del_rdisc(drp);
 475                         continue;
 476                 }
 477
 478                 LIM_SEC(rdisc_timer, drp->dr_ts+drp->dr_life+1);
 479
 480                 /* Update preference with possibly changed interface
 481                  * metric.
 482                  */
 483                 drp->dr_pref = PREF(drp->dr_recv_pref, ifp);
 484
 485                 /* Prefer the current route to prevent thrashing.
 486                  * Prefer shorter lifetimes to speed the detection of
 487                  * bad routers.
 488                  * Avoid sick interfaces.
 489                  */
 490                 if (new_drp == 0
 491                     || (!((new_st ^ drp->dr_ifp->int_state) & IS_SICK)
 492                         && (new_pref < drp->dr_pref
 493                             || (new_pref == drp->dr_pref
 494                                 && (drp == cur_drp
 495                                     || (new_drp != cur_drp
 496                                         && new_drp->dr_life > drp->dr_life)))))
 497                     || ((new_st & IS_SICK)
 498                         && !(drp->dr_ifp->int_state & IS_SICK))) {
 499                             new_drp = drp;
 500                             new_st = drp->dr_ifp->int_state;
 501                             new_pref = drp->dr_pref;
 502                 }
 503         }
 504
 505         /* switch to a better default route
 506          */
 507         if (new_drp != cur_drp) {
 508                 rt = rtget(RIP_DEFAULT, 0);
 509
 510                 /* Stop using discovered routes if they are all bad
 511                  */
 512                 if (new_drp == 0) {
 513                         trace_act("turn off Router Discovery client");
 514                         rdisc_ok = 0;
 515
 516                         if (rt != 0
 517                             && (rt->rt_state & RS_RDISC)) {
 518                                 new = rt->rt_spares[0];
 519                                 new.rts_metric = HOPCNT_INFINITY;
 520                                 new.rts_time = now.tv_sec - GARBAGE_TIME;
 521                                 rtchange(rt, rt->rt_state & ~RS_RDISC,
 522                                          &new, 0);
 523                                 rtswitch(rt, 0);
 524                         }
 525
 526                 } else {
 527                         if (cur_drp == 0) {
 528                                 trace_act("turn on Router Discovery client"
 529                                           " using %s via %s",
 530                                           naddr_ntoa(new_drp->dr_gate),
 531                                           new_drp->dr_ifp->int_name);
 532                                 rdisc_ok = 1;
 533
 534                         } else {
 535                                 trace_act("switch Router Discovery from"
 536                                           " %s via %s to %s via %s",
 537                                           naddr_ntoa(cur_drp->dr_gate),
 538                                           cur_drp->dr_ifp->int_name,
 539                                           naddr_ntoa(new_drp->dr_gate),
 540                                           new_drp->dr_ifp->int_name);
 541                         }
 542
 543                         memset(&new, 0, sizeof(new));
 544                         new.rts_ifp = new_drp->dr_ifp;
 545                         new.rts_gate = new_drp->dr_gate;
 546                         new.rts_router = new_drp->dr_gate;
 547                         new.rts_metric = HOPCNT_INFINITY-1;
 548                         new.rts_time = now.tv_sec;
 549                         if (rt != 0) {
 550                                 rtchange(rt, rt->rt_state | RS_RDISC, &new, 0);
 551                         } else {
 552                                 rtadd(RIP_DEFAULT, 0, RS_RDISC, &new);
 553                         }
 554                 }
 555
 556                 cur_drp = new_drp;
 557         }
 558
 559         /* turn RIP on or off */
 560         if (!rdisc_ok || rip_interfaces > 1) {
 561                 rip_on(0);
 562         } else {
 563                 rip_off();
 564         }
 565 }
 566
 567
 568 /* handle a single address in an advertisement
 569  */
 570 static void
 571 parse_ad(naddr from,
 572          naddr gate,
 573          n_long pref,                   /* signed and in network order */
 574          u_short life,                  /* in host byte order */
 575          struct interface *ifp)
 576 {
 577         static struct msg_limit bad_gate;
 578         struct dr *drp, *new_drp;
 579
 580
 581         if (gate == RIP_DEFAULT
 582             || !check_dst(gate)) {
 583                 msglim(&bad_gate, from,"router %s advertising bad gateway %s",
 584                        naddr_ntoa(from),
 585                        naddr_ntoa(gate));
 586                 return;
 587         }
 588
 589         /* ignore pointers to ourself and routes via unreachable networks
 590          */
 591         if (ifwithaddr(gate, 1, 0) != 0) {
 592                 trace_pkt("    discard Router Discovery Ad pointing at us");
 593                 return;
 594         }
 595         if (!on_net(gate, ifp->int_net, ifp->int_mask)) {
 596                 trace_pkt("    discard Router Discovery Ad"
 597                           " toward unreachable net");
 598                 return;
 599         }
 600
 601         /* Convert preference to an unsigned value
 602          * and later bias it by the metric of the interface.
 603          */
 604         pref = UNSIGN_PREF(ntohl(pref));
 605
 606         if (pref == 0 || life < MinMaxAdvertiseInterval) {
 607                 pref = 0;
 608                 life = 0;
 609         }
 610
 611         for (new_drp = 0, drp = drs; drp < &drs[MAX_ADS]; drp++) {
 612                 /* accept new info for a familiar entry
 613                  */
 614                 if (drp->dr_gate == gate) {
 615                         new_drp = drp;
 616                         break;
 617                 }
 618
 619                 if (life == 0)
 620                         continue;       /* do not worry about dead ads */
 621
 622                 if (drp->dr_ts == 0) {
 623                         new_drp = drp;  /* use unused entry */
 624
 625                 } else if (new_drp == 0) {
 626                         /* look for an entry worse than the new one to
 627                          * reuse.
 628                          */
 629                         if ((!(ifp->int_state & IS_SICK)
 630                              && (drp->dr_ifp->int_state & IS_SICK))
 631                             || (pref > drp->dr_pref
 632                                 && !((ifp->int_state ^ drp->dr_ifp->int_state)
 633                                      & IS_SICK)))
 634                                 new_drp = drp;
 635
 636                 } else if (new_drp->dr_ts != 0) {
 637                         /* look for the least valuable entry to reuse
 638                          */
 639                         if ((!(new_drp->dr_ifp->int_state & IS_SICK)
 640                              && (drp->dr_ifp->int_state & IS_SICK))
 641                             || (new_drp->dr_pref > drp->dr_pref
 642                                 && !((new_drp->dr_ifp->int_state
 643                                       ^ drp->dr_ifp->int_state)
 644                                      & IS_SICK)))
 645                                 new_drp = drp;
 646                 }
 647         }
 648
 649         /* forget it if all of the current entries are better */
 650         if (new_drp == 0)
 651                 return;
 652
 653         new_drp->dr_ifp = ifp;
 654         new_drp->dr_gate = gate;
 655         new_drp->dr_ts = now.tv_sec;
 656         new_drp->dr_life = life;
 657         new_drp->dr_recv_pref = pref;
 658         /* bias functional preference by metric of the interface */
 659         new_drp->dr_pref = PREF(pref,ifp);
 660
 661         /* after hearing a good advertisement, stop asking
 662          */
 663         if (!(ifp->int_state & IS_SICK))
 664                 ifp->int_rdisc_cnt = MAX_SOLICITATIONS;
 665 }
 666
 667
 668 /* Compute the IP checksum
 669  *      This assumes the packet is less than 32K long.
 670  */
 671 static u_short
 672 in_cksum(u_short *p,
 673          u_int len)
 674 {
 675         u_int sum = 0;
 676         int nwords = len >> 1;
 677
 678         while (nwords-- != 0)
 679                 sum += *p++;
 680
 681         if (len & 1)
 682                 sum += *(u_char *)p;
 683
 684         /* end-around-carry */
 685         sum = (sum >> 16) + (sum & 0xffff);
 686         sum += (sum >> 16);
 687         return (~sum);
 688 }
 689
 690
 691 /* Send a router discovery advertisement or solicitation ICMP packet.
 692  */
 693 static void
 694 send_rdisc(union ad_u *p,
 695            int p_size,
 696            struct interface *ifp,
 697            naddr dst,                   /* 0 or unicast destination */
 698            int  type)                   /* 0=unicast, 1=bcast, 2=mcast */
 699 {
 700         struct sockaddr_in rsin;
 701         int flags;
 702         const char *msg;
 703
 704
 705         memset(&rsin, 0, sizeof(rsin));
 706         rsin.sin_addr.s_addr = dst;
 707         rsin.sin_family = AF_INET;
 708 #ifdef _HAVE_SIN_LEN
 709         rsin.sin_len = sizeof(rsin);
 710 #endif
 711         flags = MSG_DONTROUTE;
 712
 713         switch (type) {
 714         case 0:                         /* unicast */
 715         default:
 716                 msg = "Send";
 717                 break;
 718
 719         case 1:                         /* broadcast */
 720                 if (ifp->int_if_flags & IFF_POINTOPOINT) {
 721                         msg = "Send pt-to-pt";
 722                         rsin.sin_addr.s_addr = ifp->int_dstaddr;
 723                 } else {
 724                         msg = "Send broadcast";
 725                         rsin.sin_addr.s_addr = ifp->int_brdaddr;
 726                 }
 727                 break;
 728
 729         case 2:                         /* multicast */
 730                 msg = "Send multicast";
 731                 if (ifp->int_state & IS_DUP) {
 732                         trace_act("abort multicast output via %s"
 733                                   " with duplicate address",
 734                                   ifp->int_name);
 735                         return;
 736                 }
 737                 if (rdisc_sock_mcast != ifp) {
 738                         /* select the right interface. */
 739                         struct ip_mreqn mreqn;
 740
 741                         memset(&mreqn, 0, sizeof(struct ip_mreqn));
 742                         mreqn.imr_ifindex = ifp->int_index;
 743                         if (0 > setsockopt(rdisc_sock,
 744                                            IPPROTO_IP, IP_MULTICAST_IF,
 745                                            &mreqn,
 746                                            sizeof(mreqn))) {
 747                                 LOGERR("setsockopt(rdisc_sock,"
 748                                        "IP_MULTICAST_IF)");
 749                                 rdisc_sock_mcast = 0;
 750                                 return;
 751                         }
 752                         rdisc_sock_mcast = ifp;
 753                 }
 754                 flags = 0;
 755                 break;
 756         }
 757
 758         if (rdisc_sock < 0)
 759                 get_rdisc_sock();
 760
 761         trace_rdisc(msg, ifp->int_addr, rsin.sin_addr.s_addr, ifp,
 762                     p, p_size);
 763
 764         if (0 > sendto(rdisc_sock, p, p_size, flags,
 765                        (struct sockaddr *)&rsin, sizeof(rsin))) {
 766                 if (ifp == 0 || !(ifp->int_state & IS_BROKE))
 767                         msglog("sendto(%s%s%s): %s",
 768                                ifp != 0 ? ifp->int_name : "",
 769                                ifp != 0 ? ", " : "",
 770                                inet_ntoa(rsin.sin_addr),
 771                                strerror(errno));
 772                 if (ifp != 0)
 773                         if_sick(ifp);
 774         }
 775 }
 776
 777
 778 /* Send an advertisement
 779  */
 780 static void
 781 send_adv(struct interface *ifp,
 782          naddr  dst,                    /* 0 or unicast destination */
 783          int    type)                   /* 0=unicast, 1=bcast, 2=mcast */
 784 {
 785         union ad_u u;
 786         n_long pref;
 787
 788
 789         memset(&u, 0, sizeof(u.ad));
 790
 791         u.ad.icmp_type = ICMP_ROUTERADVERT;
 792         u.ad.icmp_ad_num = 1;
 793         u.ad.icmp_ad_asize = sizeof(u.ad.icmp_ad_info[0])/4;
 794
 795         u.ad.icmp_ad_life = stopint ? 0 : htons(ifp->int_rdisc_int*3);
 796
 797         /* Convert the configured preference to an unsigned value,
 798          * bias it by the interface metric, and then send it as a
 799          * signed, network byte order value.
 800          */
 801         pref = UNSIGN_PREF(ifp->int_rdisc_pref);
 802         u.ad.icmp_ad_info[0].icmp_ad_pref = htonl(SIGN_PREF(PREF(pref, ifp)));
 803
 804         u.ad.icmp_ad_info[0].icmp_ad_addr = ifp->int_addr;
 805
 806         u.ad.icmp_cksum = in_cksum((u_short*)&u.ad, sizeof(u.ad));
 807
 808         send_rdisc(&u, sizeof(u.ad), ifp, dst, type);
 809 }
 810
 811
 812 /* Advertise for Router Discovery
 813  */
 814 void
 815 rdisc_adv(void)
 816 {
 817         struct interface *ifp;
 818
 819         if (!supplier)
 820                 return;
 821
 822         rdisc_timer.tv_sec = now.tv_sec + NEVER;
 823
 824         LIST_FOREACH(ifp, &ifnet, int_list) {
 825                 if (0 != (ifp->int_state & (IS_NO_ADV_OUT | IS_BROKE)))
 826                         continue;
 827
 828                 if (!timercmp(&ifp->int_rdisc_timer, &now, >)
 829                     || stopint) {
 830                         send_adv(ifp, htonl(INADDR_ALLHOSTS_GROUP),
 831                                  (ifp->int_state&IS_BCAST_RDISC) ? 1 : 2);
 832                         ifp->int_rdisc_cnt++;
 833
 834                         intvl_random(&ifp->int_rdisc_timer,
 835                                      (ifp->int_rdisc_int*3)/4,
 836                                      ifp->int_rdisc_int);
 837                         if (ifp->int_rdisc_cnt < MAX_INITIAL_ADVERTS
 838                             && (ifp->int_rdisc_timer.tv_sec
 839                                 > MAX_INITIAL_ADVERT_INTERVAL)) {
 840                                 ifp->int_rdisc_timer.tv_sec
 841                                 = MAX_INITIAL_ADVERT_INTERVAL;
 842                         }
 843                         timevaladd(&ifp->int_rdisc_timer, &now);
 844                 }
 845
 846                 if (timercmp(&rdisc_timer, &ifp->int_rdisc_timer, >))
 847                         rdisc_timer = ifp->int_rdisc_timer;
 848         }
 849 }
 850
 851
 852 /* Solicit for Router Discovery
 853  */
 854 void
 855 rdisc_sol(void)
 856 {
 857         struct interface *ifp;
 858         union ad_u u;
 859
 860
 861         if (supplier)
 862                 return;
 863
 864         rdisc_timer.tv_sec = now.tv_sec + NEVER;
 865
 866         LIST_FOREACH(ifp, &ifnet, int_list) {
 867                 if (0 != (ifp->int_state & (IS_NO_SOL_OUT | IS_BROKE))
 868                     || ifp->int_rdisc_cnt >= MAX_SOLICITATIONS)
 869                         continue;
 870
 871                 if (!timercmp(&ifp->int_rdisc_timer, &now, >)) {
 872                         memset(&u, 0, sizeof(u.so));
 873                         u.so.icmp_type = ICMP_ROUTERSOLICIT;
 874                         u.so.icmp_cksum = in_cksum((u_short*)&u.so,
 875                                                    sizeof(u.so));
 876                         send_rdisc(&u, sizeof(u.so), ifp,
 877                                    htonl(INADDR_ALLROUTERS_GROUP),
 878                                    ((ifp->int_state&IS_BCAST_RDISC) ? 1 : 2));
 879
 880                         if (++ifp->int_rdisc_cnt >= MAX_SOLICITATIONS)
 881                                 continue;
 882
 883                         ifp->int_rdisc_timer.tv_sec = SOLICITATION_INTERVAL;
 884                         ifp->int_rdisc_timer.tv_usec = 0;
 885                         timevaladd(&ifp->int_rdisc_timer, &now);
 886                 }
 887
 888                 if (timercmp(&rdisc_timer, &ifp->int_rdisc_timer, >))
 889                         rdisc_timer = ifp->int_rdisc_timer;
 890         }
 891 }
 892
 893
 894 /* check the IP header of a possible Router Discovery ICMP packet */
 895 static struct interface *               /* 0 if bad */
 896 ck_icmp(const char *act,
 897         naddr   from,
 898         struct interface *ifp,
 899         naddr   to,
 900         union ad_u *p,
 901         u_int   len)
 902 {
 903         const char *type;
 904
 905
 906         if (p->icmp.icmp_type == ICMP_ROUTERADVERT) {
 907                 type = "advertisement";
 908         } else if (p->icmp.icmp_type == ICMP_ROUTERSOLICIT) {
 909                 type = "solicitation";
 910         } else {
 911                 return 0;
 912         }
 913
 914         if (p->icmp.icmp_code != 0) {
 915                 trace_pkt("unrecognized ICMP Router %s code=%d from %s to %s",
 916                           type, p->icmp.icmp_code,
 917                           naddr_ntoa(from), naddr_ntoa(to));
 918                 return 0;
 919         }
 920
 921         trace_rdisc(act, from, to, ifp, p, len);
 922
 923         if (ifp == 0)
 924                 trace_pkt("unknown interface for router-discovery %s"
 925                           " from %s to %s",
 926                           type, naddr_ntoa(from), naddr_ntoa(to));
 927
 928         return ifp;
 929 }
 930
 931
 932 /* read packets from the router discovery socket
 933  */
 934 void
 935 read_d(void)
 936 {
 937         static struct msg_limit bad_asize, bad_len;
 938 #ifdef USE_PASSIFNAME
 939         static struct msg_limit  bad_name;
 940 #endif
 941         struct sockaddr_in from;
 942         int n, fromlen, cc, hlen;
 943         struct {
 944 #ifdef USE_PASSIFNAME
 945                 char    ifname[IFNAMSIZ];
 946 #endif
 947                 union {
 948                         struct ip ip;
 949                         u_char  b[512];
 950                 } pkt;
 951         } buf;
 952         union ad_u *p;
 953         n_long *wp;
 954         struct interface *ifp;
 955
 956
 957         for (;;) {
 958                 fromlen = sizeof(from);
 959                 cc = recvfrom(rdisc_sock, &buf, sizeof(buf), 0,
 960                               (struct sockaddr*)&from,
 961                               &fromlen);
 962                 if (cc <= 0) {
 963                         if (cc < 0 && errno != EWOULDBLOCK)
 964                                 LOGERR("recvfrom(rdisc_sock)");
 965                         break;
 966                 }
 967                 if (fromlen != sizeof(struct sockaddr_in))
 968                         logbad(1,"impossible recvfrom(rdisc_sock) fromlen=%d",
 969                                fromlen);
 970 #ifdef USE_PASSIFNAME
 971                 if ((cc -= sizeof(buf.ifname)) < 0)
 972                         logbad(0,"missing USE_PASSIFNAME; only %d bytes",
 973                                cc+sizeof(buf.ifname));
 974 #endif
 975
 976                 hlen = buf.pkt.ip.ip_hl << 2;
 977                 if (cc < hlen + ICMP_MINLEN)
 978                         continue;
 979                 p = (union ad_u *)&buf.pkt.b[hlen];
 980                 cc -= hlen;
 981
 982 #ifdef USE_PASSIFNAME
 983                 ifp = ifwithname(buf.ifname, 0);
 984                 if (ifp == 0)
 985                         msglim(&bad_name, from.sin_addr.s_addr,
 986                                "impossible rdisc if_ name %.*s",
 987                                IFNAMSIZ, buf.ifname);
 988 #else
 989                 /* If we could tell the interface on which a packet from
 990                  * address 0 arrived, we could deal with such solicitations.
 991                  */
 992                 ifp = ((from.sin_addr.s_addr == 0)
 993                        ? 0 : iflookup(from.sin_addr.s_addr));
 994 #endif
 995                 ifp = ck_icmp("Recv", from.sin_addr.s_addr, ifp,
 996                               buf.pkt.ip.ip_dst.s_addr, p, cc);
 997                 if (ifp == 0)
 998                         continue;
 999                 if (ifwithaddr(from.sin_addr.s_addr, 0, 0)) {
1000                         trace_pkt("    "
1001                                   "discard our own Router Discovery message");
1002                         continue;
1003                 }
1004
1005                 switch (p->icmp.icmp_type) {
1006                 case ICMP_ROUTERADVERT:
1007                         if (p->ad.icmp_ad_asize*4
1008                             < (int)sizeof(p->ad.icmp_ad_info[0])) {
1009                                 msglim(&bad_asize, from.sin_addr.s_addr,
1010                                        "intolerable rdisc address size=%d",
1011                                        p->ad.icmp_ad_asize);
1012                                 continue;
1013                         }
1014                         if (p->ad.icmp_ad_num == 0) {
1015                                 trace_pkt("    empty?");
1016                                 continue;
1017                         }
1018                         if (cc != (int)(sizeof(p->ad)
1019                                         - sizeof(p->ad.icmp_ad_info)
1020                                         + (p->ad.icmp_ad_num
1021                                            * sizeof(p->ad.icmp_ad_info[0])))) {
1022                                 msglim(&bad_len, from.sin_addr.s_addr,
1023                                        "rdisc length %d does not match ad_num"
1024                                        " %d", cc, p->ad.icmp_ad_num);
1025                                 continue;
1026                         }
1027                         if (supplier)
1028                                 continue;
1029                         if (ifp->int_state & IS_NO_ADV_IN)
1030                                 continue;
1031
1032                         wp = &p->ad.icmp_ad_info[0].icmp_ad_addr;
1033                         for (n = 0; n < p->ad.icmp_ad_num; n++) {
1034                                 parse_ad(from.sin_addr.s_addr,
1035                                          wp[0], wp[1],
1036                                          ntohs(p->ad.icmp_ad_life),
1037                                          ifp);
1038                                 wp += p->ad.icmp_ad_asize;
1039                         }
1040                         break;
1041
1042
1043                 case ICMP_ROUTERSOLICIT:
1044                         if (!supplier)
1045                                 continue;
1046                         if (ifp->int_state & IS_NO_ADV_OUT)
1047                                 continue;
1048                         if (stopint)
1049                                 continue;
1050
1051                         /* XXX
1052                          * We should handle messages from address 0.
1053                          */
1054
1055                         /* Respond with a point-to-point advertisement */
1056                         send_adv(ifp, from.sin_addr.s_addr, 0);
1057                         break;
1058                 }
1059         }
1060
1061         rdisc_sort();
1062 }