usr.sbin/mrouted/prune.c

   1 /*
   2  * The mrouted program is covered by the license in the accompanying file
   3  * named "LICENSE".  Use of the mrouted program represents acceptance of
   4  * the terms and conditions listed in that file.
   5  *
   6  * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
   7  * Leland Stanford Junior University.
   8  *
   9  *
  10  * prune.c,v 3.8.4.59 1998/03/01 02:06:32 fenner Exp
  11  */
  12
  13 #ifndef lint
  14 static const char rcsid[] =
  15   "$FreeBSD: src/usr.sbin/mrouted/prune.c,v 1.17.2.1 2000/10/29 03:59:57 kris Exp $";
  16 #endif /* not lint */
  17
  18 #include "defs.h"
  19
  20 extern int cache_lifetime;
  21 extern int prune_lifetime;
  22 extern struct rtentry *routing_table;
  23
  24 extern int phys_vif;
  25
  26 extern int allow_black_holes;
  27
  28 /*
  29  * randomize value to obtain a value between .5x and 1.5x
  30  * in order to prevent synchronization
  31  */
  32 #ifdef SYSV
  33 #define JITTERED_VALUE(x) ((x)/2 + (lrand48() % (x)))
  34 #else
  35 #define JITTERED_VALUE(x) ((x)/2 + (arc4random() % (x)))
  36 #endif
  37 #define CACHE_LIFETIME(x)       JITTERED_VALUE(x) /* XXX */
  38
  39 struct gtable *kernel_table;            /* ptr to list of kernel grp entries*/
  40 static struct gtable *kernel_no_route;  /* list of grp entries w/o routes   */
  41 struct gtable *gtp;                     /* pointer for kernel rt entries    */
  42 unsigned int kroutes;                   /* current number of cache entries  */
  43
  44 /****************************************************************************
  45                        Functions that are local to prune.c
  46 ****************************************************************************/
  47 static int              scoped_addr __P((vifi_t vifi, u_int32 addr));
  48 static void             prun_add_ttls __P((struct gtable *gt));
  49 static int              pruning_neighbor __P((vifi_t vifi, u_int32 addr));
  50 static int              can_mtrace __P((vifi_t vifi, u_int32 addr));
  51 static struct ptable *  find_prune_entry __P((u_int32 vr, struct ptable *pt));
  52 static void             remove_sources __P((struct gtable *gt));
  53 static void             rexmit_prune __P((void *arg));
  54 static void             expire_prune __P((vifi_t vifi, struct gtable *gt));
  55 static void             send_prune __P((struct gtable *gt));
  56 static void             send_graft __P((struct gtable *gt));
  57 static void             send_graft_ack __P((u_int32 src, u_int32 dst,
  58                                         u_int32 origin, u_int32 grp,
  59                                         vifi_t vifi));
  60 static void             update_kernel __P((struct gtable *g));
  61
  62 /*
  63  * Updates the ttl values for each vif.
  64  */
  65 static void
  66 prun_add_ttls(gt)
  67     struct gtable *gt;
  68 {
  69     struct uvif *v;
  70     vifi_t vifi;
  71
  72     for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
  73         if (VIFM_ISSET(vifi, gt->gt_grpmems))
  74             gt->gt_ttls[vifi] = v->uv_threshold;
  75         else
  76             gt->gt_ttls[vifi] = 0;
  77     }
  78 }
  79
  80 /*
  81  * checks for scoped multicast addresses
  82  * XXX I want to make the check of allow_black_holes based on ALLOW_BLACK_HOLES
  83  * but macros are not functions.
  84  */
  85 #define GET_SCOPE(gt) { \
  86         register vifi_t _i; \
  87         VIFM_CLRALL((gt)->gt_scope); \
  88         if (allow_black_holes || \
  89             (ntohl((gt)->gt_mcastgrp) & 0xff000000) == 0xef000000) \
  90             for (_i = 0; _i < numvifs; _i++) \
  91                 if (scoped_addr(_i, (gt)->gt_mcastgrp)) \
  92                     VIFM_SET(_i, (gt)->gt_scope); \
  93         } \
  94         if ((gt)->gt_route == NULL || ((gt)->gt_route->rt_parent != NO_VIF && \
  95             VIFM_ISSET((gt)->gt_route->rt_parent, (gt)->gt_scope))) \
  96                 VIFM_SETALL((gt)->gt_scope);
  97
  98 #define APPLY_SCOPE(gt) VIFM_CLR_MASK((gt)->gt_grpmems, (gt)->gt_scope)
  99
 100 #define GET_MEMBERSHIP(gt, vifi) { \
 101         if ((gt)->gt_route && \
 102             VIFM_ISSET((vifi), (gt)->gt_route->rt_children) && \
 103             (!SUBS_ARE_PRUNED((gt)->gt_route->rt_subordinates, \
 104                                 uvifs[vifi].uv_nbrmap, (gt)->gt_prunes) || \
 105              grplst_mem((vifi), (gt)->gt_mcastgrp))) \
 106                 VIFM_SET((vifi), (gt)->gt_grpmems); \
 107         }
 108
 109 static int
 110 scoped_addr(vifi, addr)
 111     vifi_t vifi;
 112     u_int32 addr;
 113 {
 114     struct vif_acl *acl;
 115
 116     for (acl = uvifs[vifi].uv_acl; acl; acl = acl->acl_next)
 117         if ((addr & acl->acl_mask) == acl->acl_addr)
 118             return 1;
 119
 120     return 0;
 121 }
 122
 123 /*
 124  * Determine the list of outgoing vifs, based upon
 125  * route subordinates, prunes received, and group
 126  * memberships.
 127  */
 128 void
 129 determine_forwvifs(gt)
 130     struct gtable *gt;
 131 {
 132     vifi_t i;
 133
 134     VIFM_CLRALL(gt->gt_grpmems);
 135     for (i = 0; i < numvifs; i++) {
 136         GET_MEMBERSHIP(gt, i);
 137     }
 138     GET_SCOPE(gt);
 139     APPLY_SCOPE(gt);
 140 }
 141
 142 /*
 143  * Send a prune or a graft if necessary.
 144  */
 145 void
 146 send_prune_or_graft(gt)
 147     struct gtable *gt;
 148 {
 149     if (VIFM_ISEMPTY(gt->gt_grpmems))
 150         send_prune(gt);
 151     else if (gt->gt_prsent_timer)
 152         send_graft(gt);
 153 }
 154
 155 /*
 156  * Determine if mcastgrp has a listener on vifi
 157  */
 158 int
 159 grplst_mem(vifi, mcastgrp)
 160     vifi_t vifi;
 161     u_int32 mcastgrp;
 162 {
 163     register struct listaddr *g;
 164     register struct uvif *v;
 165
 166     v = &uvifs[vifi];
 167
 168     for (g = v->uv_groups; g != NULL; g = g->al_next)
 169         if (mcastgrp == g->al_addr)
 170             return 1;
 171
 172     return 0;
 173 }
 174
 175 /*
 176  * Finds the group entry with the specified source and netmask.
 177  * If netmask is 0, it uses the route's netmask.
 178  *
 179  * Returns TRUE if found a match, and the global variable gtp is left
 180  * pointing to entry before the found entry.
 181  * Returns FALSE if no exact match found, gtp is left pointing to before
 182  * the entry in question belongs, or is NULL if the it belongs at the
 183  * head of the list.
 184  */
 185 int
 186 find_src_grp(src, mask, grp)
 187    u_int32 src;
 188    u_int32 mask;
 189    u_int32 grp;
 190 {
 191     struct gtable *gt;
 192
 193     gtp = NULL;
 194     gt = kernel_table;
 195     while (gt != NULL) {
 196         if (grp == gt->gt_mcastgrp &&
 197             (mask ? (gt->gt_route->rt_origin == src &&
 198                      gt->gt_route->rt_originmask == mask) :
 199                     ((src & gt->gt_route->rt_originmask) ==
 200                      gt->gt_route->rt_origin)))
 201             return TRUE;
 202         if (ntohl(grp) > ntohl(gt->gt_mcastgrp) ||
 203             (grp == gt->gt_mcastgrp &&
 204              (ntohl(mask) < ntohl(gt->gt_route->rt_originmask) ||
 205               (mask == gt->gt_route->rt_originmask &&
 206                (ntohl(src) > ntohl(gt->gt_route->rt_origin)))))) {
 207             gtp = gt;
 208             gt = gt->gt_gnext;
 209         }
 210         else break;
 211     }
 212     return FALSE;
 213 }
 214
 215 /*
 216  * Check if the neighbor supports pruning
 217  */
 218 static int
 219 pruning_neighbor(vifi, addr)
 220     vifi_t vifi;
 221     u_int32 addr;
 222 {
 223     struct listaddr *n = neighbor_info(vifi, addr);
 224     int vers;
 225
 226     if (n == NULL)
 227         return 0;
 228
 229     vers = NBR_VERS(n);
 230     return (vers >= 0x0300 && ((vers & 0xff00) != 0x0a00));
 231 }
 232
 233 /*
 234  * Can the neighbor in question handle multicast traceroute?
 235  */
 236 static int
 237 can_mtrace(vifi, addr)
 238     vifi_t      vifi;
 239     u_int32     addr;
 240 {
 241     struct listaddr *n = neighbor_info(vifi, addr);
 242     int vers;
 243
 244     if (n == NULL)
 245         return 1;       /* fail "safe" */
 246
 247     vers = NBR_VERS(n);
 248     return (vers >= 0x0303 && ((vers & 0xff00) != 0x0a00));
 249 }
 250
 251 /*
 252  * Returns the prune entry of the router, or NULL if none exists
 253  */
 254 static struct ptable *
 255 find_prune_entry(vr, pt)
 256     u_int32 vr;
 257     struct ptable *pt;
 258 {
 259     while (pt) {
 260         if (pt->pt_router == vr)
 261             return pt;
 262         pt = pt->pt_next;
 263     }
 264
 265     return NULL;
 266 }
 267
 268 /*
 269  * Remove all the sources hanging off the group table entry from the kernel
 270  * cache.  Remember the packet counts wherever possible, to keep the mtrace
 271  * counters consistent.  This prepares for possible prune retransmission,
 272  * either on a multi-access network or when a prune that we sent upstream
 273  * has expired.
 274  */
 275 static void
 276 remove_sources(gt)
 277     struct gtable *gt;
 278 {
 279     struct stable *st;
 280     struct sioc_sg_req sg_req;
 281
 282     sg_req.grp.s_addr = gt->gt_mcastgrp;
 283
 284     /*
 285      * call k_del_rg() on every one of the gt->gt_srctbl entries
 286      * but first save the packet count so that the mtrace packet
 287      * counters can remain approximately correct.  There's a race
 288      * here but it's minor.
 289      */
 290     for (st = gt->gt_srctbl; st; st = st->st_next) {
 291         if (st->st_ctime == 0)
 292             continue;
 293         IF_DEBUG(DEBUG_PRUNE)
 294         log(LOG_DEBUG, 0, "rexmit_prune deleting (%s %s) (next is %d sec)",
 295                 inet_fmt(st->st_origin, s1),
 296                 inet_fmt(gt->gt_mcastgrp, s2),
 297                 gt->gt_prune_rexmit);
 298         sg_req.src.s_addr = st->st_origin;
 299         if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
 300             sg_req.pktcnt = 0;
 301         }
 302         k_del_rg(st->st_origin, gt);
 303         st->st_ctime = 0;       /* flag that it's not in the kernel any more */
 304         st->st_savpkt += sg_req.pktcnt;
 305         kroutes--;
 306     }
 307
 308     /*
 309      * Now, add_table_entry will prune when asked to add a cache entry.
 310      */
 311 }
 312
 313 /*
 314  * Prepare for possible prune retransmission
 315  */
 316 static void
 317 rexmit_prune(arg)
 318     void *arg;
 319 {
 320     struct gtable *gt = *(struct gtable **)arg;
 321
 322     free(arg);
 323
 324     gt->gt_rexmit_timer = 0;
 325
 326     /* Make sure we're still not forwarding traffic */
 327     if (!VIFM_ISEMPTY(gt->gt_grpmems)) {
 328         IF_DEBUG(DEBUG_PRUNE)
 329         log(LOG_DEBUG, 0, "rexmit_prune (%s %s): gm:%x",
 330                 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
 331                 gt->gt_grpmems);
 332         return;
 333     }
 334
 335     remove_sources(gt);
 336 }
 337
 338 /*
 339  * Send a prune message to the dominant router for
 340  * this source.
 341  *
 342  * Record an entry that a prune was sent for this group
 343  */
 344 static void
 345 send_prune(gt)
 346     struct gtable *gt;
 347 {
 348     struct ptable *pt;
 349     char *p;
 350     int i;
 351     int datalen;
 352     u_int32 dst;
 353     u_int32 tmp;
 354     int rexmitting = 0;
 355     struct uvif *v;
 356
 357     /*
 358      * Can't process a prune if we don't have an associated route
 359      * or if the route points to a local interface.
 360      */
 361     if (gt->gt_route == NULL || gt->gt_route->rt_parent == NO_VIF ||
 362                 gt->gt_route->rt_gateway == 0)
 363         return;
 364
 365     /* Don't send a prune to a non-pruning router */
 366     if (!pruning_neighbor(gt->gt_route->rt_parent, gt->gt_route->rt_gateway))
 367         return;
 368
 369     v = &uvifs[gt->gt_route->rt_parent];
 370     /*
 371      * sends a prune message to the router upstream.
 372      */
 373 #if 0
 374     dst = v->uv_flags & VIFF_TUNNEL ? dvmrp_group : gt->gt_route->rt_gateway; /*XXX*/
 375 #else
 376     dst = gt->gt_route->rt_gateway;
 377 #endif
 378
 379     p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
 380     datalen = 0;
 381
 382     /*
 383      * determine prune lifetime, if this isn't a retransmission.
 384      *
 385      * Use interface-specified lifetime if there is one.
 386      */
 387     if (gt->gt_prsent_timer == 0) {
 388         int l = prune_lifetime;
 389
 390         if (v->uv_prune_lifetime != 0)
 391             l = v->uv_prune_lifetime;
 392
 393         gt->gt_prsent_timer = JITTERED_VALUE(l);
 394         for (pt = gt->gt_pruntbl; pt; pt = pt->pt_next)
 395             if (pt->pt_timer < gt->gt_prsent_timer)
 396                 gt->gt_prsent_timer = pt->pt_timer;
 397     } else if (gt->gt_prsent_timer < 0) {
 398         IF_DEBUG(DEBUG_PRUNE)
 399         log(LOG_DEBUG, 0, "asked to rexmit? (%s,%s)/%d on vif %d to %s with negative time",
 400             RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
 401             gt->gt_prsent_timer, gt->gt_route->rt_parent,
 402             inet_fmt(gt->gt_route->rt_gateway, s3));
 403         return;
 404     } else
 405         rexmitting = 1;
 406
 407     if (rexmitting && !(v->uv_flags & VIFF_REXMIT_PRUNES)) {
 408         IF_DEBUG(DEBUG_PRUNE)
 409         log(LOG_DEBUG, 0, "not rexmitting prune for (%s %s)/%d on vif %d to %s",
 410             RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
 411             gt->gt_prsent_timer, gt->gt_route->rt_parent,
 412             inet_fmt(gt->gt_route->rt_gateway, s3));
 413         return;
 414     }
 415     if (gt->gt_prsent_timer <= MIN_PRUNE_LIFE) {
 416         IF_DEBUG(DEBUG_PRUNE)
 417         log(LOG_DEBUG, 0, "not bothering to send prune for (%s,%s)/%d on vif %d to %s because it's too short",
 418             RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
 419             gt->gt_prsent_timer, gt->gt_route->rt_parent,
 420             inet_fmt(gt->gt_route->rt_gateway, s3));
 421         return;
 422     }
 423
 424     /*
 425      * If we have a graft pending, cancel graft retransmission
 426      */
 427     gt->gt_grftsnt = 0;
 428
 429     for (i = 0; i < 4; i++)
 430         *p++ = ((char *)&(gt->gt_route->rt_origin))[i];
 431     for (i = 0; i < 4; i++)
 432         *p++ = ((char *)&(gt->gt_mcastgrp))[i];
 433     tmp = htonl(gt->gt_prsent_timer);
 434     for (i = 0; i < 4; i++)
 435         *p++ = ((char *)&(tmp))[i];
 436     datalen += 12;
 437
 438     send_on_vif(v, dst, DVMRP_PRUNE, datalen);
 439
 440     IF_DEBUG(DEBUG_PRUNE)
 441     log(LOG_DEBUG, 0, "%s prune for (%s %s)/%d on vif %d to %s",
 442       rexmitting ? "rexmitted" : "sent",
 443       RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
 444       gt->gt_prsent_timer, gt->gt_route->rt_parent,
 445       inet_fmt(gt->gt_route->rt_gateway, s3));
 446
 447     if ((v->uv_flags & VIFF_REXMIT_PRUNES) &&
 448         gt->gt_rexmit_timer == 0 &&
 449         gt->gt_prsent_timer > gt->gt_prune_rexmit) {
 450         struct gtable **arg =
 451                     (struct gtable **)malloc(sizeof (struct gtable **));
 452
 453         *arg = gt;
 454         gt->gt_rexmit_timer = timer_setTimer(
 455                                         JITTERED_VALUE(gt->gt_prune_rexmit),
 456                                         rexmit_prune, arg);
 457         gt->gt_prune_rexmit *= 2;
 458     }
 459 }
 460
 461 /*
 462  * a prune was sent upstream
 463  * so, a graft has to be sent to annul the prune
 464  * set up a graft timer so that if an ack is not
 465  * heard within that time, another graft request
 466  * is sent out.
 467  */
 468 static void
 469 send_graft(gt)
 470     struct gtable *gt;
 471 {
 472     register char *p;
 473     register int i;
 474     int datalen;
 475     u_int32 dst;
 476
 477     /* Can't send a graft without an associated route */
 478     if (gt->gt_route == NULL || gt->gt_route->rt_parent == NO_VIF) {
 479         gt->gt_grftsnt = 0;
 480         return;
 481     }
 482
 483     gt->gt_prsent_timer = 0;
 484     gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
 485     if (gt->gt_rexmit_timer)
 486         timer_clearTimer(gt->gt_rexmit_timer);
 487
 488     if (gt->gt_grftsnt == 0)
 489         gt->gt_grftsnt = 1;
 490
 491 #if 0
 492     dst = uvifs[gt->gt_route->rt_parent].uv_flags & VIFF_TUNNEL ? dvmrp_group : gt->gt_route->rt_gateway; /*XXX*/
 493 #else
 494     dst = gt->gt_route->rt_gateway;
 495 #endif
 496
 497     p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
 498     datalen = 0;
 499
 500     for (i = 0; i < 4; i++)
 501         *p++ = ((char *)&(gt->gt_route->rt_origin))[i];
 502     for (i = 0; i < 4; i++)
 503         *p++ = ((char *)&(gt->gt_mcastgrp))[i];
 504     datalen += 8;
 505
 506     send_on_vif(&uvifs[gt->gt_route->rt_parent], dst, DVMRP_GRAFT, datalen);
 507     IF_DEBUG(DEBUG_PRUNE)
 508     log(LOG_DEBUG, 0, "sent graft for (%s %s) to %s on vif %d",
 509         RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
 510         inet_fmt(gt->gt_route->rt_gateway, s3), gt->gt_route->rt_parent);
 511 }
 512
 513 /*
 514  * Send an ack that a graft was received
 515  */
 516 static void
 517 send_graft_ack(src, dst, origin, grp, vifi)
 518     u_int32 src;
 519     u_int32 dst;
 520     u_int32 origin;
 521     u_int32 grp;
 522     vifi_t vifi;
 523 {
 524     register char *p;
 525     register int i;
 526     int datalen;
 527
 528     p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
 529     datalen = 0;
 530
 531     for (i = 0; i < 4; i++)
 532         *p++ = ((char *)&(origin))[i];
 533     for (i = 0; i < 4; i++)
 534         *p++ = ((char *)&(grp))[i];
 535     datalen += 8;
 536
 537     if (vifi == NO_VIF)
 538         send_igmp(src, dst, IGMP_DVMRP, DVMRP_GRAFT_ACK,
 539                   htonl(MROUTED_LEVEL), datalen);
 540     else {
 541 #if 0
 542         if (uvifs[vifi].uv_flags & VIFF_TUNNEL)
 543             dst = dvmrp_group;  /* XXX */
 544 #endif
 545         send_on_vif(&uvifs[vifi], dst, DVMRP_GRAFT_ACK, datalen);
 546     }
 547
 548     IF_DEBUG(DEBUG_PRUNE)
 549     if (vifi == NO_VIF)
 550         log(LOG_DEBUG, 0, "sent graft ack for (%s, %s) to %s",
 551             inet_fmt(origin, s1), inet_fmt(grp, s2), inet_fmt(dst, s3));
 552     else
 553         log(LOG_DEBUG, 0, "sent graft ack for (%s, %s) to %s on vif %d",
 554             inet_fmt(origin, s1), inet_fmt(grp, s2), inet_fmt(dst, s3), vifi);
 555 }
 556
 557 /*
 558  * Update the kernel cache with all the routes hanging off the group entry
 559  */
 560 static void
 561 update_kernel(g)
 562     struct gtable *g;
 563 {
 564     struct stable *st;
 565
 566     for (st = g->gt_srctbl; st; st = st->st_next)
 567         if (st->st_ctime != 0)
 568             k_add_rg(st->st_origin, g);
 569 }
 570
 571 /****************************************************************************
 572                           Functions that are used externally
 573 ****************************************************************************/
 574
 575 #ifdef SNMP
 576 #include <sys/types.h>
 577 #include "snmp.h"
 578
 579 /*
 580  * Find a specific group entry in the group table
 581  */
 582 struct gtable *
 583 find_grp(grp)
 584    u_int32 grp;
 585 {
 586    struct gtable *gt;
 587
 588    for (gt = kernel_table; gt; gt = gt->gt_gnext) {
 589       if (ntohl(grp) < ntohl(gt->gt_mcastgrp))
 590          break;
 591       if (gt->gt_mcastgrp == grp)
 592          return gt;
 593    }
 594    return NULL;
 595 }
 596
 597 /*
 598  * Given a group entry and source, find the corresponding source table
 599  * entry
 600  */
 601 struct stable *
 602 find_grp_src(gt, src)
 603    struct gtable *gt;
 604    u_int32 src;
 605 {
 606    struct stable *st;
 607    u_long grp = gt->gt_mcastgrp;
 608    struct gtable *gtcurr;
 609
 610    for (gtcurr = gt; gtcurr->gt_mcastgrp == grp; gtcurr = gtcurr->gt_gnext) {
 611       for (st = gtcurr->gt_srctbl; st; st = st->st_next)
 612          if (st->st_origin == src)
 613             return st;
 614    }
 615    return NULL;
 616 }
 617
 618 /*
 619  * Find next entry > specification
 620  */
 621 int
 622 next_grp_src_mask(gtpp, stpp, grp, src, mask)
 623    struct gtable **gtpp;   /* ordered by group  */
 624    struct stable **stpp;   /* ordered by source */
 625    u_int32 grp;
 626    u_int32 src;
 627    u_int32 mask;
 628 {
 629    struct gtable *gt, *gbest = NULL;
 630    struct stable *st, *sbest = NULL;
 631
 632    /* Find first group entry >= grp spec */
 633    (*gtpp) = kernel_table;
 634    while ((*gtpp) && ntohl((*gtpp)->gt_mcastgrp) < ntohl(grp))
 635       (*gtpp)=(*gtpp)->gt_gnext;
 636    if (!(*gtpp))
 637       return 0; /* no more groups */
 638
 639    for (gt = kernel_table; gt; gt=gt->gt_gnext) {
 640       /* Since grps are ordered, we can stop when group changes from gbest */
 641       if (gbest && gbest->gt_mcastgrp != gt->gt_mcastgrp)
 642          break;
 643       for (st = gt->gt_srctbl; st; st=st->st_next) {
 644
 645          /* Among those entries > spec, find "lowest" one */
 646          if (((ntohl(gt->gt_mcastgrp)> ntohl(grp))
 647            || (ntohl(gt->gt_mcastgrp)==ntohl(grp)
 648               && ntohl(st->st_origin)> ntohl(src))
 649            || (ntohl(gt->gt_mcastgrp)==ntohl(grp)
 650               && ntohl(st->st_origin)==src && 0xFFFFFFFF>ntohl(mask)))
 651           && (!gbest
 652            || (ntohl(gt->gt_mcastgrp)< ntohl(gbest->gt_mcastgrp))
 653            || (ntohl(gt->gt_mcastgrp)==ntohl(gbest->gt_mcastgrp)
 654               && ntohl(st->st_origin)< ntohl(sbest->st_origin)))) {
 655                gbest = gt;
 656                sbest = st;
 657          }
 658       }
 659    }
 660    (*gtpp) = gbest;
 661    (*stpp) = sbest;
 662    return (*gtpp)!=0;
 663 }
 664
 665 /*
 666  * Ensure that sg contains current information for the given group,source.
 667  * This is fetched from the kernel as a unit so that counts for the entry
 668  * are consistent, i.e. packet and byte counts for the same entry are
 669  * read at the same time.
 670  */
 671 void
 672 refresh_sg(sg, gt, st)
 673    struct sioc_sg_req *sg;
 674    struct gtable *gt;
 675    struct stable *st;
 676 {
 677    static   int lastq = -1;
 678
 679    if (quantum != lastq || sg->src.s_addr!=st->st_origin
 680     || sg->grp.s_addr!=gt->gt_mcastgrp) {
 681        lastq = quantum;
 682        sg->src.s_addr = st->st_origin;
 683        sg->grp.s_addr = gt->gt_mcastgrp;
 684        ioctl(udp_socket, SIOCGETSGCNT, (char *)sg);
 685    }
 686 }
 687
 688 /*
 689  * Given a routing table entry, and a vifi, find the next entry
 690  * equal to or greater than those
 691  */
 692 int
 693 next_child(gtpp, stpp, grp, src, mask, vifi)
 694    struct gtable **gtpp;
 695    struct stable **stpp;
 696    u_int32   grp;
 697    u_int32   src;
 698    u_int32   mask;
 699    vifi_t   *vifi;     /* vif at which to start looking */
 700 {
 701    /* Get (G,S,M) entry */
 702    if (mask!=0xFFFFFFFF
 703     || !((*gtpp) = find_grp(grp))
 704     || !((*stpp) = find_grp_src((*gtpp),src)))
 705       if (!next_grp_src_mask(gtpp, stpp, grp, src, mask))
 706          return 0;
 707
 708    /* Continue until we get one with a valid next vif */
 709    do {
 710       for (; (*gtpp)->gt_route->rt_children && *vifi<numvifs; (*vifi)++)
 711          if (VIFM_ISSET(*vifi, (*gtpp)->gt_route->rt_children))
 712             return 1;
 713       *vifi = 0;
 714    } while (next_grp_src_mask(gtpp, stpp, (*gtpp)->gt_mcastgrp,
 715                 (*stpp)->st_origin, 0xFFFFFFFF) );
 716
 717    return 0;
 718 }
 719 #endif /* SNMP */
 720
 721 /*
 722  * Initialize the kernel table structure
 723  */
 724 void
 725 init_ktable()
 726 {
 727     kernel_table        = NULL;
 728     kernel_no_route     = NULL;
 729     kroutes             = 0;
 730 }
 731
 732 /*
 733  * Add a new table entry for (origin, mcastgrp)
 734  */
 735 void
 736 add_table_entry(origin, mcastgrp)
 737     u_int32 origin;
 738     u_int32 mcastgrp;
 739 {
 740     struct rtentry *r;
 741     struct gtable *gt,**gtnp,*prev_gt;
 742     struct stable *st,**stnp;
 743
 744     /*
 745      * Since we have to enable mrouting to get the version number,
 746      * some cache creation requests can sneak through.  Ignore them
 747      * since we're not going to do useful stuff until we've performed
 748      * final initialization.
 749      */
 750     if (!did_final_init)
 751         return;
 752
 753 #ifdef DEBUG_MFC
 754     md_log(MD_MISS, origin, mcastgrp);
 755 #endif
 756
 757     r = determine_route(origin);
 758     prev_gt = NULL;
 759     if (r == NULL) {
 760         /*
 761          * Look for it on the no_route table; if it is found then
 762          * it will be detected as a duplicate below.
 763          */
 764         for (gt = kernel_no_route; gt; gt = gt->gt_next)
 765             if (mcastgrp == gt->gt_mcastgrp &&
 766                 gt->gt_srctbl && gt->gt_srctbl->st_origin == origin)
 767                         break;
 768         gtnp = &kernel_no_route;
 769     } else {
 770         gtnp = &r->rt_groups;
 771         while ((gt = *gtnp) != NULL) {
 772             if (gt->gt_mcastgrp >= mcastgrp)
 773                 break;
 774             gtnp = &gt->gt_next;
 775             prev_gt = gt;
 776         }
 777     }
 778
 779     if (gt == NULL || gt->gt_mcastgrp != mcastgrp) {
 780         gt = (struct gtable *)malloc(sizeof(struct gtable));
 781         if (gt == NULL)
 782             log(LOG_ERR, 0, "ran out of memory");
 783
 784         gt->gt_mcastgrp     = mcastgrp;
 785         gt->gt_timer        = CACHE_LIFETIME(cache_lifetime);
 786         time(&gt->gt_ctime);
 787         gt->gt_prsent_timer = 0;
 788         gt->gt_grftsnt      = 0;
 789         gt->gt_srctbl       = NULL;
 790         gt->gt_pruntbl      = NULL;
 791         gt->gt_route        = r;
 792         gt->gt_rexmit_timer = 0;
 793         NBRM_CLRALL(gt->gt_prunes);
 794         gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
 795 #ifdef RSRR
 796         gt->gt_rsrr_cache   = NULL;
 797 #endif
 798
 799         /* Calculate forwarding vifs */
 800         determine_forwvifs(gt);
 801
 802         /* update ttls */
 803         prun_add_ttls(gt);
 804
 805         gt->gt_next = *gtnp;
 806         *gtnp = gt;
 807         if (gt->gt_next)
 808             gt->gt_next->gt_prev = gt;
 809         gt->gt_prev = prev_gt;
 810
 811         if (r) {
 812             if (find_src_grp(r->rt_origin, r->rt_originmask, gt->gt_mcastgrp)) {
 813                 struct gtable *g;
 814
 815                 g = gtp ? gtp->gt_gnext : kernel_table;
 816                 log(LOG_WARNING, 0, "Entry for (%s %s) (rt:%x) exists (rt:%x)",
 817                     RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
 818                     r, g->gt_route);
 819             } else {
 820                 if (gtp) {
 821                     gt->gt_gnext = gtp->gt_gnext;
 822                     gt->gt_gprev = gtp;
 823                     gtp->gt_gnext = gt;
 824                 } else {
 825                     gt->gt_gnext = kernel_table;
 826                     gt->gt_gprev = NULL;
 827                     kernel_table = gt;
 828                 }
 829                 if (gt->gt_gnext)
 830                     gt->gt_gnext->gt_gprev = gt;
 831             }
 832         } else {
 833             gt->gt_gnext = gt->gt_gprev = NULL;
 834         }
 835     }
 836
 837     stnp = &gt->gt_srctbl;
 838     while ((st = *stnp) != NULL) {
 839         if (ntohl(st->st_origin) >= ntohl(origin))
 840             break;
 841         stnp = &st->st_next;
 842     }
 843
 844     if (st == NULL || st->st_origin != origin) {
 845         st = (struct stable *)malloc(sizeof(struct stable));
 846         if (st == NULL)
 847             log(LOG_ERR, 0, "ran out of memory");
 848
 849         st->st_origin = origin;
 850         st->st_pktcnt = 0;
 851         st->st_savpkt = 0;
 852         time(&st->st_ctime);
 853         st->st_next = *stnp;
 854         *stnp = st;
 855     } else {
 856         if (st->st_ctime == 0) {
 857             /* An old source which we're keeping around for statistics */
 858             time(&st->st_ctime);
 859         } else {
 860 #ifdef DEBUG_MFC
 861             md_log(MD_DUPE, origin, mcastgrp);
 862 #endif
 863             /* Ignore kernel->mrouted retransmissions */
 864             if (time(0) - st->st_ctime > 5)
 865                 log(LOG_WARNING, 0, "kernel entry already exists for (%s %s)",
 866                         inet_fmt(origin, s1), inet_fmt(mcastgrp, s2));
 867             k_add_rg(origin, gt);
 868             return;
 869         }
 870     }
 871
 872     kroutes++;
 873     k_add_rg(origin, gt);
 874
 875     IF_DEBUG(DEBUG_CACHE)
 876     log(LOG_DEBUG, 0, "add cache entry (%s %s) gm:%x, parent-vif:%d",
 877         inet_fmt(origin, s1),
 878         inet_fmt(mcastgrp, s2),
 879         gt->gt_grpmems, r ? r->rt_parent : -1);
 880
 881     /*
 882      * If there are no downstream routers that want traffic for
 883      * this group, send (or retransmit) a prune upstream.
 884      */
 885     if (VIFM_ISEMPTY(gt->gt_grpmems))
 886         send_prune(gt);
 887 }
 888
 889 /*
 890  * A router has gone down.  Remove prune state pertinent to that router.
 891  */
 892 void
 893 reset_neighbor_state(vifi, addr)
 894     vifi_t vifi;
 895     u_int32 addr;
 896 {
 897     struct rtentry *r;
 898     struct gtable *g;
 899     struct ptable *pt, **ptnp;
 900     struct stable *st;
 901
 902     for (g = kernel_table; g; g = g->gt_gnext) {
 903         r = g->gt_route;
 904
 905         /*
 906          * If neighbor was the parent, remove the prune sent state
 907          * and all of the source cache info so that prunes get
 908          * regenerated.
 909          */
 910         if (vifi == r->rt_parent) {
 911             if (addr == r->rt_gateway) {
 912                 IF_DEBUG(DEBUG_PEER)
 913                 log(LOG_DEBUG, 0, "reset_neighbor_state parent reset (%s %s)",
 914                     RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
 915
 916                 g->gt_prsent_timer = 0;
 917                 g->gt_grftsnt = 0;
 918                 while ((st = g->gt_srctbl) != NULL) {
 919                     g->gt_srctbl = st->st_next;
 920                     if (st->st_ctime != 0) {
 921                         k_del_rg(st->st_origin, g);
 922                         kroutes--;
 923                     }
 924                     free(st);
 925                 }
 926             }
 927         } else {
 928             /*
 929              * Remove any prunes that this router has sent us.
 930              */
 931             ptnp = &g->gt_pruntbl;
 932             while ((pt = *ptnp) != NULL) {
 933                 if (pt->pt_vifi == vifi && pt->pt_router == addr) {
 934                     NBRM_CLR(pt->pt_index, g->gt_prunes);
 935                     *ptnp = pt->pt_next;
 936                     free(pt);
 937                 } else
 938                     ptnp = &pt->pt_next;
 939             }
 940
 941             /*
 942              * And see if we want to forward again.
 943              */
 944             if (!VIFM_ISSET(vifi, g->gt_grpmems)) {
 945                 GET_MEMBERSHIP(g, vifi);
 946                 APPLY_SCOPE(g);
 947                 prun_add_ttls(g);
 948
 949                 /* Update kernel state */
 950                 update_kernel(g);
 951 #ifdef RSRR
 952                 /* Send route change notification to reservation protocol. */
 953                 rsrr_cache_send(g,1);
 954 #endif /* RSRR */
 955
 956                 /*
 957                  * If removing this prune causes us to start forwarding
 958                  * (e.g. the neighbor rebooted), and we sent a prune upstream,
 959                  * send a graft to cancel the prune.
 960                  */
 961                 if (!VIFM_ISEMPTY(g->gt_grpmems) && g->gt_prsent_timer)
 962                     send_graft(g);
 963
 964                 IF_DEBUG(DEBUG_PEER)
 965                 log(LOG_DEBUG, 0, "reset neighbor state (%s %s) gm:%x",
 966                     RT_FMT(r, s1),
 967                     inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
 968             }
 969         }
 970     }
 971 }
 972
 973 /*
 974  * Delete table entry from the kernel
 975  * del_flag determines how many entries to delete
 976  */
 977 void
 978 del_table_entry(r, mcastgrp, del_flag)
 979     struct rtentry *r;
 980     u_int32 mcastgrp;
 981     u_int  del_flag;
 982 {
 983     struct gtable *g, *prev_g;
 984     struct stable *st, *prev_st;
 985     struct ptable *pt, *prev_pt;
 986
 987     if (del_flag == DEL_ALL_ROUTES) {
 988         g = r->rt_groups;
 989         while (g) {
 990             IF_DEBUG(DEBUG_CACHE)
 991             log(LOG_DEBUG, 0, "del_table_entry deleting (%s %s)",
 992                 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
 993             st = g->gt_srctbl;
 994             while (st) {
 995                 if (st->st_ctime != 0) {
 996                     if (k_del_rg(st->st_origin, g) < 0) {
 997                         log(LOG_WARNING, errno,
 998                             "del_table_entry trying to delete (%s, %s)",
 999                             inet_fmt(st->st_origin, s1),
1000                             inet_fmt(g->gt_mcastgrp, s2));
1001                     }
1002                     kroutes--;
1003                 }
1004                 prev_st = st;
1005                 st = st->st_next;
1006                 free(prev_st);
1007             }
1008             g->gt_srctbl = NULL;
1009
1010             pt = g->gt_pruntbl;
1011             while (pt) {
1012                 prev_pt = pt;
1013                 pt = pt->pt_next;
1014                 free(prev_pt);
1015             }
1016             g->gt_pruntbl = NULL;
1017
1018             if (g->gt_gnext)
1019                 g->gt_gnext->gt_gprev = g->gt_gprev;
1020             if (g->gt_gprev)
1021                 g->gt_gprev->gt_gnext = g->gt_gnext;
1022             else
1023                 kernel_table = g->gt_gnext;
1024
1025 #ifdef RSRR
1026             /* Send route change notification to reservation protocol. */
1027             rsrr_cache_send(g,0);
1028             rsrr_cache_clean(g);
1029 #endif /* RSRR */
1030             if (g->gt_rexmit_timer)
1031                 timer_clearTimer(g->gt_rexmit_timer);
1032
1033             prev_g = g;
1034             g = g->gt_next;
1035             free(prev_g);
1036         }
1037         r->rt_groups = NULL;
1038     }
1039
1040     /*
1041      * Dummy routine - someday this may be needed, so it is just there
1042      */
1043     if (del_flag == DEL_RTE_GROUP) {
1044         prev_g = (struct gtable *)&r->rt_groups;
1045         for (g = r->rt_groups; g; g = g->gt_next) {
1046             if (g->gt_mcastgrp == mcastgrp) {
1047                 IF_DEBUG(DEBUG_CACHE)
1048                 log(LOG_DEBUG, 0, "del_table_entry deleting (%s %s)",
1049                     RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
1050                 st = g->gt_srctbl;
1051                 while (st) {
1052                     if (st->st_ctime != 0) {
1053                         if (k_del_rg(st->st_origin, g) < 0) {
1054                             log(LOG_WARNING, errno,
1055                                 "del_table_entry trying to delete (%s, %s)",
1056                                 inet_fmt(st->st_origin, s1),
1057                                 inet_fmt(g->gt_mcastgrp, s2));
1058                         }
1059                         kroutes--;
1060                     }
1061                     prev_st = st;
1062                     st = st->st_next;
1063                     free(prev_st);
1064                 }
1065                 g->gt_srctbl = NULL;
1066
1067                 pt = g->gt_pruntbl;
1068                 while (pt) {
1069                     prev_pt = pt;
1070                     pt = pt->pt_next;
1071                     free(prev_pt);
1072                 }
1073                 g->gt_pruntbl = NULL;
1074
1075                 if (g->gt_gnext)
1076                     g->gt_gnext->gt_gprev = g->gt_gprev;
1077                 if (g->gt_gprev)
1078                     g->gt_gprev->gt_gnext = g->gt_gnext;
1079                 else
1080                     kernel_table = g->gt_gnext;
1081
1082                 if (prev_g != (struct gtable *)&r->rt_groups)
1083                     g->gt_next->gt_prev = prev_g;
1084                 else
1085                     g->gt_next->gt_prev = NULL;
1086                 prev_g->gt_next = g->gt_next;
1087
1088                 if (g->gt_rexmit_timer)
1089                     timer_clearTimer(g->gt_rexmit_timer);
1090 #ifdef RSRR
1091                 /* Send route change notification to reservation protocol. */
1092                 rsrr_cache_send(g,0);
1093                 rsrr_cache_clean(g);
1094 #endif /* RSRR */
1095                 free(g);
1096                 g = prev_g;
1097             } else {
1098                 prev_g = g;
1099             }
1100         }
1101     }
1102 }
1103
1104 /*
1105  * update kernel table entry when a route entry changes
1106  */
1107 void
1108 update_table_entry(r, old_parent_gw)
1109     struct rtentry *r;
1110     u_int32 old_parent_gw;
1111 {
1112     struct gtable *g;
1113     struct ptable *pt, **ptnp;
1114
1115     for (g = r->rt_groups; g; g = g->gt_next) {
1116         ptnp = &g->gt_pruntbl;
1117         /*
1118          * Delete prune entries from non-children, or non-subordinates.
1119          */
1120         while ((pt = *ptnp)) {
1121             if (!VIFM_ISSET(pt->pt_vifi, r->rt_children) ||
1122                 !NBRM_ISSET(pt->pt_index, r->rt_subordinates)) {
1123
1124                 IF_DEBUG(DEBUG_PRUNE)
1125                 log(LOG_DEBUG, 0, "update_table_entry deleting prune for (%s %s) from %s on vif %d -%s%s",
1126                         RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1127                         inet_fmt(pt->pt_router, s3), pt->pt_vifi,
1128                         VIFM_ISSET(pt->pt_vifi, r->rt_children) ? "" : " not a child",
1129                         NBRM_ISSET(pt->pt_index, r->rt_subordinates) ? "" : " not a subordinate");
1130
1131                 if (!NBRM_ISSET(pt->pt_index, g->gt_prunes)) {
1132                     log(LOG_WARNING, 0,
1133                         "gt_prunes lost track of (%s %s) from %s on vif %d",
1134                         RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1135                         inet_fmt(pt->pt_router, s3), pt->pt_vifi);
1136                 }
1137
1138                 NBRM_CLR(pt->pt_index, g->gt_prunes);
1139                 *ptnp = pt->pt_next;
1140                 free(pt);
1141                 continue;
1142             }
1143             ptnp = &((*ptnp)->pt_next);
1144         }
1145
1146         IF_DEBUG(DEBUG_CACHE)
1147         log(LOG_DEBUG, 0, "updating cache entries (%s %s) old gm:%x",
1148             RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1149             g->gt_grpmems);
1150
1151         /*
1152          * Forget about a prune or graft that we sent previously if we
1153          * have a new parent router (since the new parent router will
1154          * know nothing about what I sent to the previous parent).  The
1155          * old parent will forget any prune state it is keeping for us.
1156          */
1157         if (old_parent_gw != r->rt_gateway) {
1158             g->gt_prsent_timer = 0;
1159             g->gt_grftsnt = 0;
1160         }
1161
1162         /* Recalculate membership */
1163         determine_forwvifs(g);
1164         /* send a prune or graft if needed. */
1165         send_prune_or_graft(g);
1166
1167         IF_DEBUG(DEBUG_CACHE)
1168         log(LOG_DEBUG, 0, "updating cache entries (%s %s) new gm:%x",
1169             RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1170             g->gt_grpmems);
1171
1172         /* update ttls and add entry into kernel */
1173         prun_add_ttls(g);
1174         update_kernel(g);
1175 #ifdef RSRR
1176         /* Send route change notification to reservation protocol. */
1177         rsrr_cache_send(g,1);
1178 #endif /* RSRR */
1179     }
1180 }
1181
1182 /*
1183  * set the forwarding flag for all mcastgrps on this vifi
1184  */
1185 void
1186 update_lclgrp(vifi, mcastgrp)
1187     vifi_t vifi;
1188     u_int32 mcastgrp;
1189 {
1190     struct rtentry *r;
1191     struct gtable *g;
1192
1193     IF_DEBUG(DEBUG_MEMBER)
1194     log(LOG_DEBUG, 0, "group %s joined on vif %d",
1195         inet_fmt(mcastgrp, s1), vifi);
1196
1197     for (g = kernel_table; g; g = g->gt_gnext) {
1198         if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1199             break;
1200
1201         r = g->gt_route;
1202         if (g->gt_mcastgrp == mcastgrp &&
1203             VIFM_ISSET(vifi, r->rt_children)) {
1204
1205             VIFM_SET(vifi, g->gt_grpmems);
1206             APPLY_SCOPE(g);
1207             if (VIFM_ISEMPTY(g->gt_grpmems))
1208                 continue;
1209
1210             prun_add_ttls(g);
1211             IF_DEBUG(DEBUG_CACHE)
1212             log(LOG_DEBUG, 0, "update lclgrp (%s %s) gm:%x",
1213                 RT_FMT(r, s1),
1214                 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1215
1216             update_kernel(g);
1217 #ifdef RSRR
1218             /* Send route change notification to reservation protocol. */
1219             rsrr_cache_send(g,1);
1220 #endif /* RSRR */
1221         }
1222     }
1223 }
1224
1225 /*
1226  * reset forwarding flag for all mcastgrps on this vifi
1227  */
1228 void
1229 delete_lclgrp(vifi, mcastgrp)
1230     vifi_t vifi;
1231     u_int32 mcastgrp;
1232 {
1233     struct gtable *g;
1234
1235     IF_DEBUG(DEBUG_MEMBER)
1236     log(LOG_DEBUG, 0, "group %s left on vif %d",
1237         inet_fmt(mcastgrp, s1), vifi);
1238
1239     for (g = kernel_table; g; g = g->gt_gnext) {
1240         if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1241             break;
1242
1243         if (g->gt_mcastgrp == mcastgrp && VIFM_ISSET(vifi, g->gt_grpmems)) {
1244             if (g->gt_route == NULL ||
1245                 SUBS_ARE_PRUNED(g->gt_route->rt_subordinates,
1246                         uvifs[vifi].uv_nbrmap, g->gt_prunes)) {
1247                 VIFM_CLR(vifi, g->gt_grpmems);
1248                 IF_DEBUG(DEBUG_CACHE)
1249                 log(LOG_DEBUG, 0, "delete lclgrp (%s %s) gm:%x",
1250                     RT_FMT(g->gt_route, s1),
1251                     inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1252
1253                 prun_add_ttls(g);
1254                 update_kernel(g);
1255 #ifdef RSRR
1256                 /* Send route change notification to reservation protocol. */
1257                 rsrr_cache_send(g,1);
1258 #endif /* RSRR */
1259
1260                 /*
1261                  * If there are no more members of this particular group,
1262                  *  send prune upstream
1263                  */
1264                 if (VIFM_ISEMPTY(g->gt_grpmems) && g->gt_route->rt_gateway)
1265                     send_prune(g);
1266             }
1267         }
1268     }
1269 }
1270
1271 /*
1272  * Takes the prune message received and then strips it to
1273  * determine the (src, grp) pair to be pruned.
1274  *
1275  * Adds the router to the (src, grp) entry then.
1276  *
1277  * Determines if further packets have to be sent down that vif
1278  *
1279  * Determines if a corresponding prune message has to be generated
1280  */
1281 void
1282 accept_prune(src, dst, p, datalen)
1283     u_int32 src;
1284     u_int32 dst;
1285     char *p;
1286     int datalen;
1287 {
1288     u_int32 prun_src;
1289     u_int32 prun_grp;
1290     u_int32 prun_tmr;
1291     vifi_t vifi;
1292     int i;
1293     struct rtentry *r;
1294     struct gtable *g;
1295     struct ptable *pt;
1296
1297     if ((vifi = find_vif(src, dst)) == NO_VIF) {
1298         log(LOG_INFO, 0,
1299             "ignoring prune report from non-neighbor %s",
1300             inet_fmt(src, s1));
1301         return;
1302     }
1303
1304     /* Check if enough data is present */
1305     if (datalen < 12)
1306         {
1307             log(LOG_WARNING, 0,
1308                 "non-decipherable prune from %s",
1309                 inet_fmt(src, s1));
1310             return;
1311         }
1312
1313     for (i = 0; i< 4; i++)
1314         ((char *)&prun_src)[i] = *p++;
1315     for (i = 0; i< 4; i++)
1316         ((char *)&prun_grp)[i] = *p++;
1317     for (i = 0; i< 4; i++)
1318         ((char *)&prun_tmr)[i] = *p++;
1319     prun_tmr = ntohl(prun_tmr);
1320
1321     if (prun_tmr <= MIN_PRUNE_LIFE) {
1322         IF_DEBUG(DEBUG_PRUNE)
1323         log(LOG_DEBUG, 0, "ignoring prune from %s on vif %d for (%s %s)/%d because its lifetime is too short",
1324         inet_fmt(src, s1), vifi,
1325         inet_fmt(prun_src, s2), inet_fmt(prun_grp, s3), prun_tmr);
1326         return;
1327     }
1328
1329     IF_DEBUG(DEBUG_PRUNE)
1330     log(LOG_DEBUG, 0, "%s on vif %d prunes (%s %s)/%d",
1331         inet_fmt(src, s1), vifi,
1332         inet_fmt(prun_src, s2), inet_fmt(prun_grp, s3), prun_tmr);
1333
1334     /*
1335      * Find the subnet for the prune
1336      */
1337     if (find_src_grp(prun_src, 0, prun_grp)) {
1338         g = gtp ? gtp->gt_gnext : kernel_table;
1339         r = g->gt_route;
1340
1341         IF_DEBUG(DEBUG_PRUNE)
1342         log(LOG_DEBUG, 0, "found grp state, (%s %s), metric is %d, children are %x, subords are %08x%08x",
1343                 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2), r->rt_metric,
1344                 r->rt_children, r->rt_subordinates.hi, r->rt_subordinates.lo);
1345         if (!VIFM_ISSET(vifi, r->rt_children)) {
1346             IF_DEBUG(DEBUG_PRUNE)
1347             log(LOG_WARNING, 0, "prune received from non-child %s for (%s %s) (dominant on vif %d is %s)",
1348                 inet_fmt(src, s1), inet_fmt(prun_src, s2),
1349                 inet_fmt(prun_grp, s3), vifi,
1350                 inet_fmt(r->rt_dominants[vifi], s4));
1351 #ifdef RINGBUFFER
1352             printringbuf();
1353 #endif
1354             return;
1355         }
1356         if (VIFM_ISSET(vifi, g->gt_scope)) {
1357             log(LOG_WARNING, 0, "prune received from %s on scoped grp (%s %s)",
1358                 inet_fmt(src, s1), inet_fmt(prun_src, s2),
1359                 inet_fmt(prun_grp, s3));
1360             return;
1361         }
1362         if ((pt = find_prune_entry(src, g->gt_pruntbl)) != NULL) {
1363             IF_DEBUG(DEBUG_PRUNE)
1364             log(LOG_DEBUG, 0, "%s %d from %s for (%s %s)/%d %s %d %s %x",
1365                 "duplicate prune received on vif",
1366                 vifi, inet_fmt(src, s1), inet_fmt(prun_src, s2),
1367                 inet_fmt(prun_grp, s3), prun_tmr,
1368                 "old timer:", pt->pt_timer, "cur gm:", g->gt_grpmems);
1369             pt->pt_timer = prun_tmr;
1370         } else {
1371             struct listaddr *n = neighbor_info(vifi, src);
1372
1373             if (!n) {
1374                 log(LOG_WARNING, 0, "Prune from non-neighbor %s on vif %d!?",
1375                         inet_fmt(src, s1), vifi);
1376                 return;
1377             }
1378
1379             /* allocate space for the prune structure */
1380             pt = (struct ptable *)(malloc(sizeof(struct ptable)));
1381             if (pt == NULL)
1382               log(LOG_ERR, 0, "pt: ran out of memory");
1383
1384             pt->pt_vifi = vifi;
1385             pt->pt_router = src;
1386             pt->pt_timer = prun_tmr;
1387
1388             pt->pt_next = g->gt_pruntbl;
1389             g->gt_pruntbl = pt;
1390
1391             if (n) {
1392                 pt->pt_index = n->al_index;
1393                 NBRM_SET(n->al_index, g->gt_prunes);
1394             }
1395         }
1396
1397         /*
1398          * check if any more packets need to be sent on the
1399          * vif which sent this message
1400          */
1401         if (SUBS_ARE_PRUNED(r->rt_subordinates,
1402                             uvifs[vifi].uv_nbrmap, g->gt_prunes) &&
1403                 !grplst_mem(vifi, prun_grp)) {
1404             nbrbitmap_t tmp;
1405
1406             VIFM_CLR(vifi, g->gt_grpmems);
1407             IF_DEBUG(DEBUG_PRUNE)
1408             log(LOG_DEBUG, 0, "vifnbrs=0x%08x%08x, subord=0x%08x%08x prunes=0x%08x%08x",
1409                 uvifs[vifi].uv_nbrmap.hi,uvifs[vifi].uv_nbrmap.lo,
1410                 r->rt_subordinates.hi, r->rt_subordinates.lo,
1411                 g->gt_prunes.hi, g->gt_prunes.lo);
1412             /* XXX debugging */
1413             NBRM_COPY(r->rt_subordinates, tmp);
1414             NBRM_MASK(tmp, uvifs[vifi].uv_nbrmap);
1415             if (!NBRM_ISSETALLMASK(g->gt_prunes, tmp))
1416                 log(LOG_WARNING, 0, "subordinate error");
1417             /* XXX end debugging */
1418             IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1419             log(LOG_DEBUG, 0, "prune (%s %s), stop sending on vif %d, gm:%x",
1420                 RT_FMT(r, s1),
1421                 inet_fmt(g->gt_mcastgrp, s2), vifi, g->gt_grpmems);
1422
1423             prun_add_ttls(g);
1424             update_kernel(g);
1425 #ifdef RSRR
1426             /* Send route change notification to reservation protocol. */
1427             rsrr_cache_send(g,1);
1428 #endif /* RSRR */
1429         }
1430
1431         /*
1432          * check if all the child routers have expressed no interest
1433          * in this group and if this group does not exist in the
1434          * interface
1435          * Send a prune message then upstream
1436          */
1437         if (VIFM_ISEMPTY(g->gt_grpmems) && r->rt_gateway) {
1438             send_prune(g);
1439         }
1440     } else {
1441         /*
1442          * There is no kernel entry for this group.  Therefore, we can
1443          * simply ignore the prune, as we are not forwarding this traffic
1444          * downstream.
1445          */
1446         IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1447         log(LOG_DEBUG, 0, "%s (%s %s)/%d from %s",
1448             "prune message received with no kernel entry for",
1449             inet_fmt(prun_src, s1), inet_fmt(prun_grp, s2),
1450             prun_tmr, inet_fmt(src, s3));
1451         return;
1452     }
1453 }
1454
1455 /*
1456  * Checks if this mcastgrp is present in the kernel table
1457  * If so and if a prune was sent, it sends a graft upwards
1458  */
1459 void
1460 chkgrp_graft(vifi, mcastgrp)
1461     vifi_t      vifi;
1462     u_int32     mcastgrp;
1463 {
1464     struct rtentry *r;
1465     struct gtable *g;
1466
1467     for (g = kernel_table; g; g = g->gt_gnext) {
1468         if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1469             break;
1470
1471         r = g->gt_route;
1472         if (g->gt_mcastgrp == mcastgrp && VIFM_ISSET(vifi, r->rt_children))
1473             if (g->gt_prsent_timer) {
1474                 VIFM_SET(vifi, g->gt_grpmems);
1475
1476                 /*
1477                  * If the vif that was joined was a scoped vif,
1478                  * ignore it ; don't graft back
1479                  */
1480                 APPLY_SCOPE(g);
1481                 if (VIFM_ISEMPTY(g->gt_grpmems))
1482                     continue;
1483
1484                 /* send graft upwards */
1485                 send_graft(g);
1486
1487                 /* update cache timer*/
1488                 g->gt_timer = CACHE_LIFETIME(cache_lifetime);
1489
1490                 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1491                 log(LOG_DEBUG, 0, "chkgrp graft (%s %s) gm:%x",
1492                     RT_FMT(r, s1),
1493                     inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1494
1495                 prun_add_ttls(g);
1496                 update_kernel(g);
1497 #ifdef RSRR
1498                 /* Send route change notification to reservation protocol. */
1499                 rsrr_cache_send(g,1);
1500 #endif /* RSRR */
1501             }
1502     }
1503 }
1504
1505 /* determine the multicast group and src
1506  *
1507  * if it does, then determine if a prune was sent
1508  * upstream.
1509  * if prune sent upstream, send graft upstream and send
1510  * ack downstream.
1511  *
1512  * if no prune sent upstream, change the forwarding bit
1513  * for this interface and send ack downstream.
1514  *
1515  * if no entry exists for this group send ack downstream.
1516  */
1517 void
1518 accept_graft(src, dst, p, datalen)
1519     u_int32     src;
1520     u_int32     dst;
1521     char        *p;
1522     int         datalen;
1523 {
1524     vifi_t      vifi;
1525     u_int32     graft_src;
1526     u_int32     graft_grp;
1527     int         i;
1528     struct rtentry *r;
1529     struct gtable *g;
1530     struct ptable *pt, **ptnp;
1531
1532     if (datalen < 8) {
1533         log(LOG_WARNING, 0,
1534             "received non-decipherable graft from %s",
1535             inet_fmt(src, s1));
1536         return;
1537     }
1538
1539     for (i = 0; i< 4; i++)
1540         ((char *)&graft_src)[i] = *p++;
1541     for (i = 0; i< 4; i++)
1542         ((char *)&graft_grp)[i] = *p++;
1543
1544     vifi = find_vif(src, dst);
1545     send_graft_ack(dst, src, graft_src, graft_grp, vifi);
1546
1547     if (vifi == NO_VIF) {
1548         log(LOG_INFO, 0,
1549             "ignoring graft for (%s %s) from non-neighbor %s",
1550             inet_fmt(graft_src, s2), inet_fmt(graft_grp, s3),
1551             inet_fmt(src, s1));
1552         return;
1553     }
1554
1555     IF_DEBUG(DEBUG_PRUNE)
1556     log(LOG_DEBUG, 0, "%s on vif %d grafts (%s %s)",
1557         inet_fmt(src, s1), vifi,
1558         inet_fmt(graft_src, s2), inet_fmt(graft_grp, s3));
1559
1560     /*
1561      * Find the subnet for the graft
1562      */
1563     if (find_src_grp(graft_src, 0, graft_grp)) {
1564         g = gtp ? gtp->gt_gnext : kernel_table;
1565         r = g->gt_route;
1566
1567         if (VIFM_ISSET(vifi, g->gt_scope)) {
1568             log(LOG_WARNING, 0, "graft received from %s on scoped grp (%s %s)",
1569                 inet_fmt(src, s1), inet_fmt(graft_src, s2),
1570                 inet_fmt(graft_grp, s3));
1571             return;
1572         }
1573
1574         ptnp = &g->gt_pruntbl;
1575         while ((pt = *ptnp) != NULL) {
1576             if ((pt->pt_vifi == vifi) && (pt->pt_router == src)) {
1577                 NBRM_CLR(pt->pt_index, g->gt_prunes);
1578                 *ptnp = pt->pt_next;
1579                 free(pt);
1580
1581                 VIFM_SET(vifi, g->gt_grpmems);
1582                 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1583                 log(LOG_DEBUG, 0, "accept graft (%s %s) gm:%x",
1584                     RT_FMT(r, s1),
1585                     inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1586
1587                 prun_add_ttls(g);
1588                 update_kernel(g);
1589 #ifdef RSRR
1590                 /* Send route change notification to reservation protocol. */
1591                 rsrr_cache_send(g,1);
1592 #endif /* RSRR */
1593                 break;
1594             } else {
1595                 ptnp = &pt->pt_next;
1596             }
1597         }
1598
1599         g->gt_timer = CACHE_LIFETIME(cache_lifetime);
1600
1601         if (g->gt_prsent_timer)
1602             /* send graft upwards */
1603             send_graft(g);
1604     } else {
1605         /*
1606          * We have no state for the source and group in question.
1607          * This is fine, since we know that we have no prune state, and
1608          * grafts are requests to remove prune state.
1609          */
1610         IF_DEBUG(DEBUG_PRUNE)
1611         log(LOG_DEBUG, 0, "%s (%s %s) from %s",
1612             "graft received with no kernel entry for",
1613             inet_fmt(graft_src, s1), inet_fmt(graft_grp, s2),
1614             inet_fmt(src, s3));
1615         return;
1616     }
1617 }
1618
1619 /*
1620  * find out which group is involved first of all
1621  * then determine if a graft was sent.
1622  * if no graft sent, ignore the message
1623  * if graft was sent and the ack is from the right
1624  * source, remove the graft timer so that we don't
1625  * have send a graft again
1626  */
1627 void
1628 accept_g_ack(src, dst, p, datalen)
1629     u_int32     src;
1630     u_int32     dst;
1631     char        *p;
1632     int         datalen;
1633 {
1634     struct gtable *g;
1635     vifi_t      vifi;
1636     u_int32     grft_src;
1637     u_int32     grft_grp;
1638     int         i;
1639
1640     if ((vifi = find_vif(src, dst)) == NO_VIF) {
1641         log(LOG_INFO, 0,
1642             "ignoring graft ack from non-neighbor %s",
1643             inet_fmt(src, s1));
1644         return;
1645     }
1646
1647     if (datalen < 0  || datalen > 8) {
1648         log(LOG_WARNING, 0,
1649             "received non-decipherable graft ack from %s",
1650             inet_fmt(src, s1));
1651         return;
1652     }
1653
1654     for (i = 0; i< 4; i++)
1655         ((char *)&grft_src)[i] = *p++;
1656     for (i = 0; i< 4; i++)
1657         ((char *)&grft_grp)[i] = *p++;
1658
1659     IF_DEBUG(DEBUG_PRUNE)
1660     log(LOG_DEBUG, 0, "%s on vif %d acks graft (%s, %s)",
1661         inet_fmt(src, s1), vifi,
1662         inet_fmt(grft_src, s2), inet_fmt(grft_grp, s3));
1663
1664     /*
1665      * Find the subnet for the graft ack
1666      */
1667     if (find_src_grp(grft_src, 0, grft_grp)) {
1668         g = gtp ? gtp->gt_gnext : kernel_table;
1669         g->gt_grftsnt = 0;
1670     } else {
1671         log(LOG_WARNING, 0, "%s (%s, %s) from %s",
1672             "rcvd graft ack with no kernel entry for",
1673             inet_fmt(grft_src, s1), inet_fmt(grft_grp, s2),
1674             inet_fmt(src, s3));
1675 #ifdef RINGBUFFER
1676         printringbuf();
1677 #endif
1678         return;
1679     }
1680 }
1681
1682
1683 /*
1684  * free all prune entries and kernel routes
1685  * normally, this should inform the kernel that all of its routes
1686  * are going away, but this is only called by restart(), which is
1687  * about to call MRT_DONE which does that anyway.
1688  */
1689 void
1690 free_all_prunes()
1691 {
1692     register struct rtentry *r;
1693     register struct gtable *g, *prev_g;
1694     register struct stable *s, *prev_s;
1695     register struct ptable *p, *prev_p;
1696
1697     for (r = routing_table; r; r = r->rt_next) {
1698         g = r->rt_groups;
1699         while (g) {
1700             s = g->gt_srctbl;
1701             while (s) {
1702                 prev_s = s;
1703                 s = s->st_next;
1704                 free(prev_s);
1705             }
1706
1707             p = g->gt_pruntbl;
1708             while (p) {
1709                 prev_p = p;
1710                 p = p->pt_next;
1711                 free(prev_p);
1712             }
1713
1714             prev_g = g;
1715             g = g->gt_next;
1716             if (prev_g->gt_rexmit_timer)
1717                 timer_clearTimer(prev_g->gt_rexmit_timer);
1718             free(prev_g);
1719         }
1720         r->rt_groups = NULL;
1721     }
1722     kernel_table = NULL;
1723
1724     g = kernel_no_route;
1725     while (g) {
1726         if (g->gt_srctbl)
1727             free(g->gt_srctbl);
1728
1729         prev_g = g;
1730         g = g->gt_next;
1731         if (prev_g->gt_rexmit_timer)
1732             timer_clearTimer(prev_g->gt_rexmit_timer);
1733         free(prev_g);
1734     }
1735     kernel_no_route = NULL;
1736 }
1737
1738 /*
1739  * When a new route is created, search
1740  * a) The less-specific part of the routing table
1741  * b) The route-less kernel table
1742  * for sources that the new route might want to handle.
1743  *
1744  * "Inheriting" these sources might be cleanest, but simply deleting
1745  * them is easier, and letting the kernel re-request them.
1746  */
1747 void
1748 steal_sources(rt)
1749     struct rtentry *rt;
1750 {
1751     register struct rtentry *rp;
1752     register struct gtable *gt, **gtnp;
1753     register struct stable *st, **stnp;
1754
1755     for (rp = rt->rt_next; rp; rp = rp->rt_next) {
1756         if (rp->rt_groups == NULL)
1757             continue;
1758         if ((rt->rt_origin & rp->rt_originmask) == rp->rt_origin) {
1759             IF_DEBUG(DEBUG_ROUTE)
1760             log(LOG_DEBUG, 0, "Route for %s stealing sources from %s",
1761                 RT_FMT(rt, s1), RT_FMT(rp, s2));
1762             for (gt = rp->rt_groups; gt; gt = gt->gt_next) {
1763                 stnp = &gt->gt_srctbl;
1764                 while ((st = *stnp) != NULL) {
1765                     if ((st->st_origin & rt->rt_originmask) == rt->rt_origin) {
1766                         IF_DEBUG(DEBUG_ROUTE)
1767                         log(LOG_DEBUG, 0, "%s stealing (%s %s) from %s",
1768                             RT_FMT(rt, s1),
1769                             inet_fmt(st->st_origin, s3),
1770                             inet_fmt(gt->gt_mcastgrp, s4),
1771                             RT_FMT(rp, s2));
1772                         if (st->st_ctime != 0) {
1773                             if (k_del_rg(st->st_origin, gt) < 0) {
1774                                 log(LOG_WARNING, errno, "%s (%s, %s)",
1775                                     "steal_sources trying to delete",
1776                                     inet_fmt(st->st_origin, s1),
1777                                     inet_fmt(gt->gt_mcastgrp, s2));
1778                             }
1779                             kroutes--;
1780                         }
1781                         *stnp = st->st_next;
1782                         free(st);
1783                     } else {
1784                         stnp = &st->st_next;
1785                     }
1786                 }
1787             }
1788         }
1789     }
1790
1791     gtnp = &kernel_no_route;
1792     while ((gt = *gtnp) != NULL) {
1793         if (gt->gt_srctbl && ((gt->gt_srctbl->st_origin & rt->rt_originmask)
1794                                     == rt->rt_origin)) {
1795             IF_DEBUG(DEBUG_ROUTE)
1796             log(LOG_DEBUG, 0, "%s stealing (%s %s) from %s",
1797                 RT_FMT(rt, s1),
1798                 inet_fmt(gt->gt_srctbl->st_origin, s3),
1799                 inet_fmt(gt->gt_mcastgrp, s4),
1800                 "no_route table");
1801             if (gt->gt_srctbl->st_ctime != 0) {
1802                 if (k_del_rg(gt->gt_srctbl->st_origin, gt) < 0) {
1803                     log(LOG_WARNING, errno, "%s (%s %s)",
1804                         "steal_sources trying to delete",
1805                         inet_fmt(gt->gt_srctbl->st_origin, s1),
1806                         inet_fmt(gt->gt_mcastgrp, s2));
1807                 }
1808                 kroutes--;
1809             }
1810             free(gt->gt_srctbl);
1811             *gtnp = gt->gt_next;
1812             if (gt->gt_next)
1813                 gt->gt_next->gt_prev = gt->gt_prev;
1814             if (gt->gt_rexmit_timer)
1815                 timer_clearTimer(gt->gt_rexmit_timer);
1816             free(gt);
1817         } else {
1818             gtnp = &gt->gt_next;
1819         }
1820     }
1821 }
1822
1823 /*
1824  * Advance the timers on all the cache entries.
1825  * If there are any entries whose timers have expired,
1826  * remove these entries from the kernel cache.
1827  */
1828 void
1829 age_table_entry()
1830 {
1831     struct rtentry *r;
1832     struct gtable *gt, **gtnptr;
1833     struct stable *st, **stnp;
1834     struct ptable *pt, **ptnp;
1835     struct sioc_sg_req sg_req;
1836
1837     IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1838     log(LOG_DEBUG, 0, "aging forwarding cache entries");
1839
1840     gtnptr = &kernel_table;
1841     while ((gt = *gtnptr) != NULL) {
1842         vifi_t i; /* XXX Debugging */
1843         int fixit = 0; /* XXX Debugging */
1844
1845         r = gt->gt_route;
1846
1847         /* XXX Debugging... */
1848         for (i = 0; i < numvifs; i++) {
1849             /*
1850              * If we're not sending on this vif,
1851              * And this group isn't scoped on this vif,
1852              * And I'm the parent for this route on this vif,
1853              * And there are subordinates on this vif,
1854              * And all of the subordinates haven't pruned,
1855              *          YELL LOUDLY
1856              *          and remember to fix it up later
1857              */
1858             if (!VIFM_ISSET(i, gt->gt_grpmems) &&
1859                 !VIFM_ISSET(i, gt->gt_scope) &&
1860                 VIFM_ISSET(i, r->rt_children) &&
1861                 NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates) &&
1862                 !SUBS_ARE_PRUNED(r->rt_subordinates, uvifs[i].uv_nbrmap, gt->gt_prunes)) {
1863                 log(LOG_WARNING, 0, "(%s %s) is blackholing on vif %d",
1864                     RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), i);
1865                 fixit = 1;
1866             }
1867         }
1868         if (fixit) {
1869             log(LOG_WARNING, 0, "fixing membership for (%s %s) gm:%x",
1870                 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems);
1871             determine_forwvifs(gt);
1872             send_prune_or_graft(gt);
1873             log(LOG_WARNING, 0, "fixed  membership for (%s %s) gm:%x",
1874                 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems);
1875 #ifdef RINGBUFFER
1876             printringbuf();
1877 #endif
1878         }
1879         /*DEBUG2*/
1880         /* If there are group members,
1881          * and there are recent sources,
1882          * and we have a route,
1883          * and it's not directly connected,
1884          * and we haven't sent a prune,
1885          *      if there are any cache entries in the kernel
1886          *       [if there aren't we're probably waiting to rexmit],
1887          *              YELL LOUDLY
1888          *              and send a prune
1889          */
1890         if (VIFM_ISEMPTY(gt->gt_grpmems) && gt->gt_srctbl && r && r->rt_gateway && gt->gt_prsent_timer == 0) {
1891             for (st = gt->gt_srctbl; st; st = st->st_next)
1892                 if (st->st_ctime != 0)
1893                     break;
1894             if (st != NULL) {
1895                 log(LOG_WARNING, 0, "grpmems for (%s %s) is empty but no prune state!", RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
1896                 send_prune_or_graft(gt);
1897 #ifdef RINGBUFFER
1898                 printringbuf();
1899 #endif
1900             }
1901         }
1902         /* XXX ...Debugging */
1903
1904         /* advance the timer for the kernel entry */
1905         gt->gt_timer -= TIMER_INTERVAL;
1906
1907         /* decrement prune timer if need be */
1908         if (gt->gt_prsent_timer > 0) {
1909             gt->gt_prsent_timer -= TIMER_INTERVAL;
1910             if (gt->gt_prsent_timer <= 0) {
1911                 IF_DEBUG(DEBUG_PRUNE)
1912                 log(LOG_DEBUG, 0, "upstream prune tmo (%s %s)",
1913                     RT_FMT(r, s1),
1914                     inet_fmt(gt->gt_mcastgrp, s2));
1915                 gt->gt_prsent_timer = -1;
1916                 /* Reset the prune retransmission timer to its initial value */
1917                 gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
1918             }
1919         }
1920
1921         /* retransmit graft with exponential backoff */
1922         if (gt->gt_grftsnt) {
1923             register int y;
1924
1925             y = ++gt->gt_grftsnt;
1926             while (y && !(y & 1))
1927                 y >>= 1;
1928             if (y == 1)
1929                 send_graft(gt);
1930         }
1931
1932         /*
1933          * Age prunes
1934          *
1935          * If a prune expires, forward again on that vif.
1936          */
1937         ptnp = &gt->gt_pruntbl;
1938         while ((pt = *ptnp) != NULL) {
1939             if ((pt->pt_timer -= TIMER_INTERVAL) <= 0) {
1940                 IF_DEBUG(DEBUG_PRUNE)
1941                 log(LOG_DEBUG, 0, "expire prune (%s %s) from %s on vif %d",
1942                     RT_FMT(r, s1),
1943                     inet_fmt(gt->gt_mcastgrp, s2),
1944                     inet_fmt(pt->pt_router, s3),
1945                     pt->pt_vifi);
1946                 if (gt->gt_prsent_timer > 0) {
1947                     log(LOG_WARNING, 0, "prune (%s %s) from %s on vif %d expires with %d left on prsent timer",
1948                         RT_FMT(r, s1),
1949                         inet_fmt(gt->gt_mcastgrp, s2),
1950                         inet_fmt(pt->pt_router, s3),
1951                         pt->pt_vifi, gt->gt_prsent_timer);
1952                     /* Send a graft to heal the tree. */
1953                     send_graft(gt);
1954                 }
1955
1956                 NBRM_CLR(pt->pt_index, gt->gt_prunes);
1957                 expire_prune(pt->pt_vifi, gt);
1958
1959                 /* remove the router's prune entry and await new one */
1960                 *ptnp = pt->pt_next;
1961                 free(pt);
1962             } else {
1963                 ptnp = &pt->pt_next;
1964             }
1965         }
1966
1967         /*
1968          * If the cache entry has expired, delete source table entries for
1969          * silent sources.  If there are no source entries left, and there
1970          * are no downstream prunes, then the entry is deleted.
1971          * Otherwise, the cache entry's timer is refreshed.
1972          */
1973         if (gt->gt_timer <= 0) {
1974             IF_DEBUG(DEBUG_CACHE)
1975             log(LOG_DEBUG, 0, "(%s %s) timed out, checking for traffic",
1976                 RT_FMT(gt->gt_route, s1),
1977                 inet_fmt(gt->gt_mcastgrp, s2));
1978             /* Check for traffic before deleting source entries */
1979             sg_req.grp.s_addr = gt->gt_mcastgrp;
1980             stnp = &gt->gt_srctbl;
1981             while ((st = *stnp) != NULL) {
1982                 /*
1983                  * Source entries with no ctime are not actually in the
1984                  * kernel; they have been removed by rexmit_prune() so
1985                  * are safe to remove from the list at this point.
1986                  */
1987                 if (st->st_ctime) {
1988                     sg_req.src.s_addr = st->st_origin;
1989                     if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
1990                         log(LOG_WARNING, errno, "%s (%s %s)",
1991                             "age_table_entry: SIOCGETSGCNT failing for",
1992                             inet_fmt(st->st_origin, s1),
1993                             inet_fmt(gt->gt_mcastgrp, s2));
1994                         /* Make sure it gets deleted below */
1995                         sg_req.pktcnt = st->st_pktcnt;
1996                     }
1997                 } else {
1998                     sg_req.pktcnt = st->st_pktcnt;
1999                 }
2000                 if (sg_req.pktcnt == st->st_pktcnt) {
2001                     *stnp = st->st_next;
2002                     IF_DEBUG(DEBUG_CACHE)
2003                     log(LOG_DEBUG, 0, "age_table_entry deleting (%s %s)",
2004                         inet_fmt(st->st_origin, s1),
2005                         inet_fmt(gt->gt_mcastgrp, s2));
2006                     if (st->st_ctime != 0) {
2007                         if (k_del_rg(st->st_origin, gt) < 0) {
2008                             log(LOG_WARNING, errno,
2009                                 "age_table_entry trying to delete (%s %s)",
2010                                 inet_fmt(st->st_origin, s1),
2011                                 inet_fmt(gt->gt_mcastgrp, s2));
2012                         }
2013                         kroutes--;
2014                     }
2015                     free(st);
2016                 } else {
2017                     st->st_pktcnt = sg_req.pktcnt;
2018                     stnp = &st->st_next;
2019                 }
2020             }
2021
2022             /*
2023              * Retain the group entry if we have downstream prunes or if
2024              * there is at least one source in the list that still has
2025              * traffic, or if our upstream prune timer or graft
2026              * retransmission timer is running.
2027              */
2028             if (gt->gt_pruntbl != NULL || gt->gt_srctbl != NULL ||
2029                 gt->gt_prsent_timer > 0 || gt->gt_grftsnt > 0) {
2030                 IF_DEBUG(DEBUG_CACHE)
2031                 log(LOG_DEBUG, 0, "refresh lifetim of cache entry %s%s%s%s(%s, %s)",
2032                         gt->gt_pruntbl ? "(dstrm prunes) " : "",
2033                         gt->gt_srctbl ? "(trfc flow) " : "",
2034                         gt->gt_prsent_timer > 0 ? "(upstrm prune) " : "",
2035                         gt->gt_grftsnt > 0 ? "(grft rexmit) " : "",
2036                         RT_FMT(r, s1),
2037                         inet_fmt(gt->gt_mcastgrp, s2));
2038                 gt->gt_timer = CACHE_LIFETIME(cache_lifetime);
2039                 if (gt->gt_prsent_timer == -1) {
2040                     /*
2041                      * The upstream prune timed out.  Remove any kernel
2042                      * state.
2043                      */
2044                     gt->gt_prsent_timer = 0;
2045                     if (gt->gt_pruntbl) {
2046                         log(LOG_WARNING, 0, "upstream prune for (%s %s) expires with downstream prunes active",
2047                                 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
2048                     }
2049                     remove_sources(gt);
2050                 }
2051                 gtnptr = &gt->gt_gnext;
2052                 continue;
2053             }
2054
2055             IF_DEBUG(DEBUG_CACHE)
2056             log(LOG_DEBUG, 0, "timeout cache entry (%s, %s)",
2057                 RT_FMT(r, s1),
2058                 inet_fmt(gt->gt_mcastgrp, s2));
2059
2060             if (gt->gt_prev)
2061                 gt->gt_prev->gt_next = gt->gt_next;
2062             else
2063                 gt->gt_route->rt_groups = gt->gt_next;
2064             if (gt->gt_next)
2065                 gt->gt_next->gt_prev = gt->gt_prev;
2066
2067             if (gt->gt_gprev) {
2068                 gt->gt_gprev->gt_gnext = gt->gt_gnext;
2069                 gtnptr = &gt->gt_gprev->gt_gnext;
2070             } else {
2071                 kernel_table = gt->gt_gnext;
2072                 gtnptr = &kernel_table;
2073             }
2074             if (gt->gt_gnext)
2075                 gt->gt_gnext->gt_gprev = gt->gt_gprev;
2076
2077 #ifdef RSRR
2078             /* Send route change notification to reservation protocol. */
2079             rsrr_cache_send(gt,0);
2080             rsrr_cache_clean(gt);
2081 #endif /* RSRR */
2082             if (gt->gt_rexmit_timer)
2083                 timer_clearTimer(gt->gt_rexmit_timer);
2084
2085             free((char *)gt);
2086         } else {
2087             if (gt->gt_prsent_timer == -1) {
2088                 /*
2089                  * The upstream prune timed out.  Remove any kernel
2090                  * state.
2091                  */
2092                 gt->gt_prsent_timer = 0;
2093                 if (gt->gt_pruntbl) {
2094                     log(LOG_WARNING, 0, "upstream prune for (%s %s) expires with downstream prunes active",
2095                             RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
2096                 }
2097                 remove_sources(gt);
2098             }
2099             gtnptr = &gt->gt_gnext;
2100         }
2101     }
2102
2103     /*
2104      * When traversing the no_route table, the decision is much easier.
2105      * Just delete it if it has timed out.
2106      */
2107     gtnptr = &kernel_no_route;
2108     while ((gt = *gtnptr) != NULL) {
2109         /* advance the timer for the kernel entry */
2110         gt->gt_timer -= TIMER_INTERVAL;
2111
2112         if (gt->gt_timer < 0) {
2113             if (gt->gt_srctbl) {
2114                 if (gt->gt_srctbl->st_ctime != 0) {
2115                     if (k_del_rg(gt->gt_srctbl->st_origin, gt) < 0) {
2116                         log(LOG_WARNING, errno, "%s (%s %s)",
2117                             "age_table_entry trying to delete no-route",
2118                             inet_fmt(gt->gt_srctbl->st_origin, s1),
2119                             inet_fmt(gt->gt_mcastgrp, s2));
2120                     }
2121                     kroutes--;
2122                 }
2123                 free(gt->gt_srctbl);
2124             }
2125             *gtnptr = gt->gt_next;
2126             if (gt->gt_next)
2127                 gt->gt_next->gt_prev = gt->gt_prev;
2128
2129             if (gt->gt_rexmit_timer)
2130                 timer_clearTimer(gt->gt_rexmit_timer);
2131
2132             free((char *)gt);
2133         } else {
2134             gtnptr = &gt->gt_next;
2135         }
2136     }
2137 }
2138
2139 /*
2140  * Modify the kernel to forward packets when one or multiple prunes that
2141  * were received on the vif given by vifi, for the group given by gt,
2142  * have expired.
2143  */
2144 static void
2145 expire_prune(vifi, gt)
2146      vifi_t vifi;
2147      struct gtable *gt;
2148 {
2149     /*
2150      * No need to send a graft, any prunes that we sent
2151      * will expire before any prunes that we have received.
2152      * However, in the case that we did make a mistake,
2153      * send a graft to compensate.
2154      */
2155     if (gt->gt_prsent_timer >= MIN_PRUNE_LIFE) {
2156         IF_DEBUG(DEBUG_PRUNE)
2157         log(LOG_DEBUG, 0, "prune expired with %d left on %s",
2158                 gt->gt_prsent_timer, "prsent_timer");
2159         gt->gt_prsent_timer = 0;
2160         send_graft(gt);
2161     }
2162
2163     /* modify the kernel entry to forward packets */
2164     if (!VIFM_ISSET(vifi, gt->gt_grpmems)) {
2165         struct rtentry *rt = gt->gt_route;
2166         VIFM_SET(vifi, gt->gt_grpmems);
2167         IF_DEBUG(DEBUG_CACHE)
2168         log(LOG_DEBUG, 0, "forw again (%s %s) gm:%x vif:%d",
2169         RT_FMT(rt, s1),
2170         inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems, vifi);
2171
2172         prun_add_ttls(gt);
2173         update_kernel(gt);
2174 #ifdef RSRR
2175         /* Send route change notification to reservation protocol. */
2176         rsrr_cache_send(gt,1);
2177 #endif /* RSRR */
2178     }
2179 }
2180
2181 /*
2182  * Print the contents of the cache table on file 'fp2'.
2183  */
2184 void
2185 dump_cache(fp2)
2186     FILE *fp2;
2187 {
2188     register struct rtentry *r;
2189     register struct gtable *gt;
2190     register struct stable *st;
2191     register struct ptable *pt;
2192     register vifi_t i;
2193     char c;
2194     register time_t thyme = time(0);
2195
2196     fprintf(fp2,
2197             "Multicast Routing Cache Table (%d entries)\n%s", kroutes,
2198     " Origin             Mcast-group         CTmr     Age      Ptmr Rx IVif Forwvifs\n");
2199     fprintf(fp2,
2200     "<(prunesrc:vif[idx]/tmr) prunebitmap\n%s",
2201     ">Source             Lifetime SavPkt         Pkts    Bytes RPFf\n");
2202
2203     for (gt = kernel_no_route; gt; gt = gt->gt_next) {
2204         if (gt->gt_srctbl) {
2205             fprintf(fp2, " %-18s %-15s %-8s %-8s        - -1 (no route)\n",
2206                 inet_fmts(gt->gt_srctbl->st_origin, 0xffffffff, s1),
2207                 inet_fmt(gt->gt_mcastgrp, s2), scaletime(gt->gt_timer),
2208                 scaletime(thyme - gt->gt_ctime));
2209             fprintf(fp2, ">%s\n", inet_fmt(gt->gt_srctbl->st_origin, s1));
2210         }
2211     }
2212
2213     for (gt = kernel_table; gt; gt = gt->gt_gnext) {
2214         r = gt->gt_route;
2215         fprintf(fp2, " %-18s %-15s",
2216             RT_FMT(r, s1),
2217             inet_fmt(gt->gt_mcastgrp, s2));
2218
2219         fprintf(fp2, " %-8s", scaletime(gt->gt_timer));
2220
2221         fprintf(fp2, " %-8s %-8s ", scaletime(thyme - gt->gt_ctime),
2222                         gt->gt_prsent_timer ? scaletime(gt->gt_prsent_timer) :
2223                                               "       -");
2224
2225         if (gt->gt_prune_rexmit) {
2226             int i = gt->gt_prune_rexmit;
2227             int n = 0;
2228
2229             while (i > PRUNE_REXMIT_VAL) {
2230                 n++;
2231                 i /= 2;
2232             }
2233             if (n == 0 && gt->gt_prsent_timer == 0)
2234                 fprintf(fp2, " -");
2235             else
2236                 fprintf(fp2, "%2d", n);
2237         } else {
2238             fprintf(fp2, " -");
2239         }
2240
2241         fprintf(fp2, " %2u%c%c", r->rt_parent,
2242             gt->gt_prsent_timer ? 'P' :
2243                                   gt->gt_grftsnt ? 'G' : ' ',
2244             VIFM_ISSET(r->rt_parent, gt->gt_scope) ? 'B' : ' ');
2245
2246         for (i = 0; i < numvifs; ++i) {
2247             if (VIFM_ISSET(i, gt->gt_grpmems))
2248                 fprintf(fp2, " %u ", i);
2249             else if (VIFM_ISSET(i, r->rt_children) &&
2250                      NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
2251                 fprintf(fp2, " %u%c", i,
2252                         VIFM_ISSET(i, gt->gt_scope) ? 'b' :
2253                         SUBS_ARE_PRUNED(r->rt_subordinates,
2254                             uvifs[i].uv_nbrmap, gt->gt_prunes) ? 'p' : '!');
2255         }
2256         fprintf(fp2, "\n");
2257         if (gt->gt_pruntbl) {
2258             fprintf(fp2, "<");
2259             c = '(';
2260             for (pt = gt->gt_pruntbl; pt; pt = pt->pt_next) {
2261                 fprintf(fp2, "%c%s:%d[%d]/%d", c, inet_fmt(pt->pt_router, s1),
2262                     pt->pt_vifi, pt->pt_index, pt->pt_timer);
2263                 c = ',';
2264             }
2265             fprintf(fp2, ")");
2266             fprintf(fp2, " 0x%08lx%08lx\n",/*XXX*/
2267                     gt->gt_prunes.hi, gt->gt_prunes.lo);
2268         }
2269         for (st = gt->gt_srctbl; st; st = st->st_next) {
2270             fprintf(fp2, ">%-18s %-8s %6ld", inet_fmt(st->st_origin, s1),
2271                 st->st_ctime ? scaletime(thyme - st->st_ctime) : "-",
2272                 st->st_savpkt);
2273             if (st->st_ctime) {
2274                 struct sioc_sg_req sg_req;
2275
2276                 sg_req.src.s_addr = st->st_origin;
2277                 sg_req.grp.s_addr = gt->gt_mcastgrp;
2278                 if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
2279                     log(LOG_WARNING, errno, "SIOCGETSGCNT on (%s %s)",
2280                         inet_fmt(st->st_origin, s1),
2281                         inet_fmt(gt->gt_mcastgrp, s2));
2282                 } else {
2283                     fprintf(fp2, "     %8ld %8ld %4ld", sg_req.pktcnt,
2284                         sg_req.bytecnt, sg_req.wrong_if);
2285                 }
2286             }
2287             fprintf(fp2, "\n");
2288         }
2289     }
2290 }
2291
2292 /*
2293  * Traceroute function which returns traceroute replies to the requesting
2294  * router. Also forwards the request to downstream routers.
2295  */
2296 void
2297 accept_mtrace(src, dst, group, data, no, datalen)
2298     u_int32 src;
2299     u_int32 dst;
2300     u_int32 group;
2301     char *data;
2302     u_int no;   /* promoted u_char */
2303     int datalen;
2304 {
2305     u_char type;
2306     struct rtentry *rt;
2307     struct gtable *gt;
2308     struct tr_query *qry;
2309     struct tr_resp  *resp;
2310     int vifi;
2311     char *p;
2312     int rcount;
2313     int errcode = TR_NO_ERR;
2314     int resptype;
2315     struct timeval tp;
2316     struct sioc_vif_req v_req;
2317     struct sioc_sg_req sg_req;
2318
2319     /* Remember qid across invocations */
2320     static u_int32 oqid = 0;
2321
2322     /* timestamp the request/response */
2323     gettimeofday(&tp, 0);
2324
2325     /*
2326      * Check if it is a query or a response
2327      */
2328     if (datalen == QLEN) {
2329         type = QUERY;
2330         IF_DEBUG(DEBUG_TRACE)
2331         log(LOG_DEBUG, 0, "Initial traceroute query rcvd from %s to %s",
2332             inet_fmt(src, s1), inet_fmt(dst, s2));
2333     }
2334     else if ((datalen - QLEN) % RLEN == 0) {
2335         type = RESP;
2336         IF_DEBUG(DEBUG_TRACE)
2337         log(LOG_DEBUG, 0, "In-transit traceroute query rcvd from %s to %s",
2338             inet_fmt(src, s1), inet_fmt(dst, s2));
2339         if (IN_MULTICAST(ntohl(dst))) {
2340             IF_DEBUG(DEBUG_TRACE)
2341             log(LOG_DEBUG, 0, "Dropping multicast response");
2342             return;
2343         }
2344     }
2345     else {
2346         log(LOG_WARNING, 0, "%s from %s to %s",
2347             "Non decipherable traceroute request recieved",
2348             inet_fmt(src, s1), inet_fmt(dst, s2));
2349         return;
2350     }
2351
2352     qry = (struct tr_query *)data;
2353
2354     /*
2355      * if it is a packet with all reports filled, drop it
2356      */
2357     if ((rcount = (datalen - QLEN)/RLEN) == no) {
2358         IF_DEBUG(DEBUG_TRACE)
2359         log(LOG_DEBUG, 0, "packet with all reports filled in");
2360         return;
2361     }
2362
2363     IF_DEBUG(DEBUG_TRACE) {
2364     log(LOG_DEBUG, 0, "s: %s g: %s d: %s ", inet_fmt(qry->tr_src, s1),
2365             inet_fmt(group, s2), inet_fmt(qry->tr_dst, s3));
2366     log(LOG_DEBUG, 0, "rttl: %d rd: %s", qry->tr_rttl,
2367             inet_fmt(qry->tr_raddr, s1));
2368     log(LOG_DEBUG, 0, "rcount:%d, qid:%06x", rcount, qry->tr_qid);
2369     }
2370
2371     /* determine the routing table entry for this traceroute */
2372     rt = determine_route(qry->tr_src);
2373     IF_DEBUG(DEBUG_TRACE)
2374     if (rt) {
2375         log(LOG_DEBUG, 0, "rt parent vif: %d rtr: %s metric: %d",
2376                 rt->rt_parent, inet_fmt(rt->rt_gateway, s1), rt->rt_metric);
2377         log(LOG_DEBUG, 0, "rt origin %s",
2378                 RT_FMT(rt, s1));
2379     } else
2380         log(LOG_DEBUG, 0, "...no route");
2381
2382     /*
2383      * Query type packet - check if rte exists
2384      * Check if the query destination is a vif connected to me.
2385      * and if so, whether I should start response back
2386      */
2387     if (type == QUERY) {
2388         if (oqid == qry->tr_qid) {
2389             /*
2390              * If the multicast router is a member of the group being
2391              * queried, and the query is multicasted, then the router can
2392              * recieve multiple copies of the same query.  If we have already
2393              * replied to this traceroute, just ignore it this time.
2394              *
2395              * This is not a total solution, but since if this fails you
2396              * only get N copies, N <= the number of interfaces on the router,
2397              * it is not fatal.
2398              */
2399             IF_DEBUG(DEBUG_TRACE)
2400             log(LOG_DEBUG, 0, "ignoring duplicate traceroute packet");
2401             return;
2402         }
2403
2404         if (rt == NULL) {
2405             IF_DEBUG(DEBUG_TRACE)
2406             log(LOG_DEBUG, 0, "Mcast traceroute: no route entry %s",
2407                    inet_fmt(qry->tr_src, s1));
2408             if (IN_MULTICAST(ntohl(dst)))
2409                 return;
2410         }
2411         vifi = find_vif(qry->tr_dst, 0);
2412
2413         if (vifi == NO_VIF) {
2414             /* The traceroute destination is not on one of my subnet vifs. */
2415             IF_DEBUG(DEBUG_TRACE)
2416             log(LOG_DEBUG, 0, "Destination %s not an interface",
2417                    inet_fmt(qry->tr_dst, s1));
2418             if (IN_MULTICAST(ntohl(dst)))
2419                 return;
2420             errcode = TR_WRONG_IF;
2421         } else if (rt != NULL && !VIFM_ISSET(vifi, rt->rt_children)) {
2422             IF_DEBUG(DEBUG_TRACE)
2423             log(LOG_DEBUG, 0, "Destination %s not on forwarding tree for src %s",
2424                    inet_fmt(qry->tr_dst, s1), inet_fmt(qry->tr_src, s2));
2425             if (IN_MULTICAST(ntohl(dst)))
2426                 return;
2427             errcode = TR_WRONG_IF;
2428         }
2429     }
2430     else {
2431         /*
2432          * determine which interface the packet came in on
2433          * RESP packets travel hop-by-hop so this either traversed
2434          * a tunnel or came from a directly attached mrouter.
2435          */
2436         if ((vifi = find_vif(src, dst)) == NO_VIF) {
2437             IF_DEBUG(DEBUG_TRACE)
2438             log(LOG_DEBUG, 0, "Wrong interface for packet");
2439             errcode = TR_WRONG_IF;
2440         }
2441     }
2442
2443     /* Now that we've decided to send a response, save the qid */
2444     oqid = qry->tr_qid;
2445
2446     IF_DEBUG(DEBUG_TRACE)
2447     log(LOG_DEBUG, 0, "Sending traceroute response");
2448
2449     /* copy the packet to the sending buffer */
2450     p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
2451
2452     bcopy(data, p, datalen);
2453
2454     p += datalen;
2455
2456     /*
2457      * If there is no room to insert our reply, coopt the previous hop
2458      * error indication to relay this fact.
2459      */
2460     if (p + sizeof(struct tr_resp) > send_buf + RECV_BUF_SIZE) {
2461         resp = (struct tr_resp *)p - 1;
2462         resp->tr_rflags = TR_NO_SPACE;
2463         rt = NULL;
2464         goto sendit;
2465     }
2466
2467     /*
2468      * fill in initial response fields
2469      */
2470     resp = (struct tr_resp *)p;
2471     bzero(resp, sizeof(struct tr_resp));
2472     datalen += RLEN;
2473
2474     resp->tr_qarr    = htonl(((tp.tv_sec + JAN_1970) << 16) +
2475                                 ((tp.tv_usec << 10) / 15625));
2476
2477     resp->tr_rproto  = PROTO_DVMRP;
2478     resp->tr_outaddr = (vifi == NO_VIF) ? dst : uvifs[vifi].uv_lcl_addr;
2479     resp->tr_fttl    = (vifi == NO_VIF) ? 0 : uvifs[vifi].uv_threshold;
2480     resp->tr_rflags  = errcode;
2481
2482     /*
2483      * obtain # of packets out on interface
2484      */
2485     v_req.vifi = vifi;
2486     if (vifi != NO_VIF && ioctl(udp_socket, SIOCGETVIFCNT, (char *)&v_req) >= 0)
2487         resp->tr_vifout  =  htonl(v_req.ocount);
2488     else
2489         resp->tr_vifout  =  0xffffffff;
2490
2491     /*
2492      * fill in scoping & pruning information
2493      */
2494     if (rt)
2495         for (gt = rt->rt_groups; gt; gt = gt->gt_next) {
2496             if (gt->gt_mcastgrp >= group)
2497                 break;
2498         }
2499     else
2500         gt = NULL;
2501
2502     if (gt && gt->gt_mcastgrp == group) {
2503         struct stable *st;
2504
2505         for (st = gt->gt_srctbl; st; st = st->st_next)
2506             if (qry->tr_src == st->st_origin)
2507                 break;
2508
2509         sg_req.src.s_addr = qry->tr_src;
2510         sg_req.grp.s_addr = group;
2511         if (st && st->st_ctime != 0 &&
2512                   ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) >= 0)
2513             resp->tr_pktcnt = htonl(sg_req.pktcnt + st->st_savpkt);
2514         else
2515             resp->tr_pktcnt = htonl(st ? st->st_savpkt : 0xffffffff);
2516
2517         if (VIFM_ISSET(vifi, gt->gt_scope))
2518             resp->tr_rflags = TR_SCOPED;
2519         else if (gt->gt_prsent_timer)
2520             resp->tr_rflags = TR_PRUNED;
2521         else if (!VIFM_ISSET(vifi, gt->gt_grpmems))
2522             if (!NBRM_ISEMPTY(uvifs[vifi].uv_nbrmap) &&
2523                 SUBS_ARE_PRUNED(rt->rt_subordinates,
2524                                 uvifs[vifi].uv_nbrmap, gt->gt_prunes))
2525                 resp->tr_rflags = TR_OPRUNED;
2526             else
2527                 resp->tr_rflags = TR_NO_FWD;
2528     } else {
2529         if ((vifi != NO_VIF && scoped_addr(vifi, group)) ||
2530             (rt && scoped_addr(rt->rt_parent, group)))
2531             resp->tr_rflags = TR_SCOPED;
2532         else if (rt && !VIFM_ISSET(vifi, rt->rt_children))
2533             resp->tr_rflags = TR_NO_FWD;
2534     }
2535
2536     /*
2537      *  if no rte exists, set NO_RTE error
2538      */
2539     if (rt == NULL) {
2540         src = dst;              /* the dst address of resp. pkt */
2541         resp->tr_inaddr   = 0;
2542         resp->tr_rflags   = TR_NO_RTE;
2543         resp->tr_rmtaddr  = 0;
2544     } else {
2545         /* get # of packets in on interface */
2546         v_req.vifi = rt->rt_parent;
2547         if (ioctl(udp_socket, SIOCGETVIFCNT, (char *)&v_req) >= 0)
2548             resp->tr_vifin = htonl(v_req.icount);
2549         else
2550             resp->tr_vifin = 0xffffffff;
2551
2552         MASK_TO_VAL(rt->rt_originmask, resp->tr_smask);
2553         src = uvifs[rt->rt_parent].uv_lcl_addr;
2554         resp->tr_inaddr = src;
2555         resp->tr_rmtaddr = rt->rt_gateway;
2556         if (!VIFM_ISSET(vifi, rt->rt_children)) {
2557             IF_DEBUG(DEBUG_TRACE)
2558             log(LOG_DEBUG, 0, "Destination %s not on forwarding tree for src %s",
2559                    inet_fmt(qry->tr_dst, s1), inet_fmt(qry->tr_src, s2));
2560             resp->tr_rflags = TR_WRONG_IF;
2561         }
2562         if (rt->rt_metric >= UNREACHABLE) {
2563             resp->tr_rflags = TR_NO_RTE;
2564             /* Hack to send reply directly */
2565             rt = NULL;
2566         }
2567     }
2568
2569 sendit:
2570     /*
2571      * if metric is 1 or no. of reports is 1, send response to requestor
2572      * else send to upstream router.  If the upstream router can't handle
2573      * mtrace, set an error code and send to requestor anyway.
2574      */
2575     IF_DEBUG(DEBUG_TRACE)
2576     log(LOG_DEBUG, 0, "rcount:%d, no:%d", rcount, no);
2577
2578     if ((rcount + 1 == no) || (rt == NULL) || (rt->rt_metric == 1)) {
2579         resptype = IGMP_MTRACE_RESP;
2580         dst = qry->tr_raddr;
2581     } else
2582         if (!can_mtrace(rt->rt_parent, rt->rt_gateway)) {
2583             dst = qry->tr_raddr;
2584             resp->tr_rflags = TR_OLD_ROUTER;
2585             resptype = IGMP_MTRACE_RESP;
2586         } else {
2587             dst = rt->rt_gateway;
2588             resptype = IGMP_MTRACE;
2589         }
2590
2591     if (IN_MULTICAST(ntohl(dst))) {
2592         /*
2593          * Send the reply on a known multicast capable vif.
2594          * If we don't have one, we can't source any multicasts anyway.
2595          */
2596         if (phys_vif != -1) {
2597             IF_DEBUG(DEBUG_TRACE)
2598             log(LOG_DEBUG, 0, "Sending reply to %s from %s",
2599                 inet_fmt(dst, s1), inet_fmt(uvifs[phys_vif].uv_lcl_addr, s2));
2600             k_set_ttl(qry->tr_rttl);
2601             send_igmp(uvifs[phys_vif].uv_lcl_addr, dst,
2602                       resptype, no, group,
2603                       datalen);
2604             k_set_ttl(1);
2605         } else
2606             log(LOG_INFO, 0, "No enabled phyints -- %s",
2607                         "dropping traceroute reply");
2608     } else {
2609         IF_DEBUG(DEBUG_TRACE)
2610         log(LOG_DEBUG, 0, "Sending %s to %s from %s",
2611             resptype == IGMP_MTRACE_RESP ?  "reply" : "request on",
2612             inet_fmt(dst, s1), inet_fmt(src, s2));
2613
2614         send_igmp(src, dst,
2615                   resptype, no, group,
2616                   datalen);
2617     }
2618     return;
2619 }