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