usr.sbin/mrouted/prune.c

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