"Fossies" - the Fresh Open Source Software Archive

Member "mrouted-3.9.8/prune.c" (1 Jan 2017, 67973 Bytes) of package /linux/misc/mrouted-3.9.8.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "prune.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 3.9.7_vs_3.9.8.

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