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