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