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.
6 * The mrouted program is COPYRIGHT 1989 by The Board of Trustees of
7 * Leland Stanford Junior University.
10 * prune.c,v 3.8.4.59 1998/03/01 02:06:32 fenner Exp
12 * $FreeBSD: src/usr.sbin/mrouted/prune.c,v 1.17.2.1 2000/10/29 03:59:57 kris Exp $
13 * $DragonFly: src/usr.sbin/mrouted/prune.c,v 1.3 2003/11/03 19:31:38 eirikn Exp $
18 extern int cache_lifetime;
19 extern int prune_lifetime;
20 extern struct rtentry *routing_table;
24 extern int allow_black_holes;
27 * randomize value to obtain a value between .5x and 1.5x
28 * in order to prevent synchronization
31 #define JITTERED_VALUE(x) ((x)/2 + (lrand48() % (x)))
33 #define JITTERED_VALUE(x) ((x)/2 + (arc4random() % (x)))
35 #define CACHE_LIFETIME(x) JITTERED_VALUE(x) /* XXX */
37 struct gtable *kernel_table; /* ptr to list of kernel grp entries*/
38 static struct gtable *kernel_no_route; /* list of grp entries w/o routes */
39 struct gtable *gtp; /* pointer for kernel rt entries */
40 unsigned int kroutes; /* current number of cache entries */
42 /****************************************************************************
43 Functions that are local to prune.c
44 ****************************************************************************/
45 static int scoped_addr(vifi_t vifi, u_int32 addr);
46 static void prun_add_ttls(struct gtable *gt);
47 static int pruning_neighbor(vifi_t vifi, u_int32 addr);
48 static int can_mtrace(vifi_t vifi, u_int32 addr);
49 static struct ptable * find_prune_entry(u_int32 vr, struct ptable *pt);
50 static void remove_sources(struct gtable *gt);
51 static void rexmit_prune(void *arg);
52 static void expire_prune(vifi_t vifi, struct gtable *gt);
53 static void send_prune(struct gtable *gt);
54 static void send_graft(struct gtable *gt);
55 static void send_graft_ack(u_int32 src, u_int32 dst,
56 u_int32 origin, u_int32 grp,
58 static void update_kernel(struct gtable *g);
61 * Updates the ttl values for each vif.
70 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
71 if (VIFM_ISSET(vifi, gt->gt_grpmems))
72 gt->gt_ttls[vifi] = v->uv_threshold;
74 gt->gt_ttls[vifi] = 0;
79 * checks for scoped multicast addresses
80 * XXX I want to make the check of allow_black_holes based on ALLOW_BLACK_HOLES
81 * but macros are not functions.
83 #define GET_SCOPE(gt) { \
85 VIFM_CLRALL((gt)->gt_scope); \
86 if (allow_black_holes || \
87 (ntohl((gt)->gt_mcastgrp) & 0xff000000) == 0xef000000) \
88 for (_i = 0; _i < numvifs; _i++) \
89 if (scoped_addr(_i, (gt)->gt_mcastgrp)) \
90 VIFM_SET(_i, (gt)->gt_scope); \
92 if ((gt)->gt_route == NULL || ((gt)->gt_route->rt_parent != NO_VIF && \
93 VIFM_ISSET((gt)->gt_route->rt_parent, (gt)->gt_scope))) \
94 VIFM_SETALL((gt)->gt_scope);
96 #define APPLY_SCOPE(gt) VIFM_CLR_MASK((gt)->gt_grpmems, (gt)->gt_scope)
98 #define GET_MEMBERSHIP(gt, vifi) { \
99 if ((gt)->gt_route && \
100 VIFM_ISSET((vifi), (gt)->gt_route->rt_children) && \
101 (!SUBS_ARE_PRUNED((gt)->gt_route->rt_subordinates, \
102 uvifs[vifi].uv_nbrmap, (gt)->gt_prunes) || \
103 grplst_mem((vifi), (gt)->gt_mcastgrp))) \
104 VIFM_SET((vifi), (gt)->gt_grpmems); \
108 scoped_addr(vifi, addr)
114 for (acl = uvifs[vifi].uv_acl; acl; acl = acl->acl_next)
115 if ((addr & acl->acl_mask) == acl->acl_addr)
122 * Determine the list of outgoing vifs, based upon
123 * route subordinates, prunes received, and group
127 determine_forwvifs(gt)
132 VIFM_CLRALL(gt->gt_grpmems);
133 for (i = 0; i < numvifs; i++) {
134 GET_MEMBERSHIP(gt, i);
141 * Send a prune or a graft if necessary.
144 send_prune_or_graft(gt)
147 if (VIFM_ISEMPTY(gt->gt_grpmems))
149 else if (gt->gt_prsent_timer)
154 * Determine if mcastgrp has a listener on vifi
157 grplst_mem(vifi, mcastgrp)
161 register struct listaddr *g;
162 register struct uvif *v;
166 for (g = v->uv_groups; g != NULL; g = g->al_next)
167 if (mcastgrp == g->al_addr)
174 * Finds the group entry with the specified source and netmask.
175 * If netmask is 0, it uses the route's netmask.
177 * Returns TRUE if found a match, and the global variable gtp is left
178 * pointing to entry before the found entry.
179 * Returns FALSE if no exact match found, gtp is left pointing to before
180 * the entry in question belongs, or is NULL if the it belongs at the
184 find_src_grp(src, mask, grp)
194 if (grp == gt->gt_mcastgrp &&
195 (mask ? (gt->gt_route->rt_origin == src &&
196 gt->gt_route->rt_originmask == mask) :
197 ((src & gt->gt_route->rt_originmask) ==
198 gt->gt_route->rt_origin)))
200 if (ntohl(grp) > ntohl(gt->gt_mcastgrp) ||
201 (grp == gt->gt_mcastgrp &&
202 (ntohl(mask) < ntohl(gt->gt_route->rt_originmask) ||
203 (mask == gt->gt_route->rt_originmask &&
204 (ntohl(src) > ntohl(gt->gt_route->rt_origin)))))) {
214 * Check if the neighbor supports pruning
217 pruning_neighbor(vifi, addr)
221 struct listaddr *n = neighbor_info(vifi, addr);
228 return (vers >= 0x0300 && ((vers & 0xff00) != 0x0a00));
232 * Can the neighbor in question handle multicast traceroute?
235 can_mtrace(vifi, addr)
239 struct listaddr *n = neighbor_info(vifi, addr);
243 return 1; /* fail "safe" */
246 return (vers >= 0x0303 && ((vers & 0xff00) != 0x0a00));
250 * Returns the prune entry of the router, or NULL if none exists
252 static struct ptable *
253 find_prune_entry(vr, pt)
258 if (pt->pt_router == vr)
267 * Remove all the sources hanging off the group table entry from the kernel
268 * cache. Remember the packet counts wherever possible, to keep the mtrace
269 * counters consistent. This prepares for possible prune retransmission,
270 * either on a multi-access network or when a prune that we sent upstream
278 struct sioc_sg_req sg_req;
280 sg_req.grp.s_addr = gt->gt_mcastgrp;
283 * call k_del_rg() on every one of the gt->gt_srctbl entries
284 * but first save the packet count so that the mtrace packet
285 * counters can remain approximately correct. There's a race
286 * here but it's minor.
288 for (st = gt->gt_srctbl; st; st = st->st_next) {
289 if (st->st_ctime == 0)
291 IF_DEBUG(DEBUG_PRUNE)
292 log(LOG_DEBUG, 0, "rexmit_prune deleting (%s %s) (next is %d sec)",
293 inet_fmt(st->st_origin, s1),
294 inet_fmt(gt->gt_mcastgrp, s2),
295 gt->gt_prune_rexmit);
296 sg_req.src.s_addr = st->st_origin;
297 if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
300 k_del_rg(st->st_origin, gt);
301 st->st_ctime = 0; /* flag that it's not in the kernel any more */
302 st->st_savpkt += sg_req.pktcnt;
307 * Now, add_table_entry will prune when asked to add a cache entry.
312 * Prepare for possible prune retransmission
318 struct gtable *gt = *(struct gtable **)arg;
322 gt->gt_rexmit_timer = 0;
324 /* Make sure we're still not forwarding traffic */
325 if (!VIFM_ISEMPTY(gt->gt_grpmems)) {
326 IF_DEBUG(DEBUG_PRUNE)
327 log(LOG_DEBUG, 0, "rexmit_prune (%s %s): gm:%x",
328 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
337 * Send a prune message to the dominant router for
340 * Record an entry that a prune was sent for this group
356 * Can't process a prune if we don't have an associated route
357 * or if the route points to a local interface.
359 if (gt->gt_route == NULL || gt->gt_route->rt_parent == NO_VIF ||
360 gt->gt_route->rt_gateway == 0)
363 /* Don't send a prune to a non-pruning router */
364 if (!pruning_neighbor(gt->gt_route->rt_parent, gt->gt_route->rt_gateway))
367 v = &uvifs[gt->gt_route->rt_parent];
369 * sends a prune message to the router upstream.
372 dst = v->uv_flags & VIFF_TUNNEL ? dvmrp_group : gt->gt_route->rt_gateway; /*XXX*/
374 dst = gt->gt_route->rt_gateway;
377 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
381 * determine prune lifetime, if this isn't a retransmission.
383 * Use interface-specified lifetime if there is one.
385 if (gt->gt_prsent_timer == 0) {
386 int l = prune_lifetime;
388 if (v->uv_prune_lifetime != 0)
389 l = v->uv_prune_lifetime;
391 gt->gt_prsent_timer = JITTERED_VALUE(l);
392 for (pt = gt->gt_pruntbl; pt; pt = pt->pt_next)
393 if (pt->pt_timer < gt->gt_prsent_timer)
394 gt->gt_prsent_timer = pt->pt_timer;
395 } else if (gt->gt_prsent_timer < 0) {
396 IF_DEBUG(DEBUG_PRUNE)
397 log(LOG_DEBUG, 0, "asked to rexmit? (%s,%s)/%d on vif %d to %s with negative time",
398 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
399 gt->gt_prsent_timer, gt->gt_route->rt_parent,
400 inet_fmt(gt->gt_route->rt_gateway, s3));
405 if (rexmitting && !(v->uv_flags & VIFF_REXMIT_PRUNES)) {
406 IF_DEBUG(DEBUG_PRUNE)
407 log(LOG_DEBUG, 0, "not rexmitting prune for (%s %s)/%d on vif %d to %s",
408 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
409 gt->gt_prsent_timer, gt->gt_route->rt_parent,
410 inet_fmt(gt->gt_route->rt_gateway, s3));
413 if (gt->gt_prsent_timer <= MIN_PRUNE_LIFE) {
414 IF_DEBUG(DEBUG_PRUNE)
415 log(LOG_DEBUG, 0, "not bothering to send prune for (%s,%s)/%d on vif %d to %s because it's too short",
416 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
417 gt->gt_prsent_timer, gt->gt_route->rt_parent,
418 inet_fmt(gt->gt_route->rt_gateway, s3));
423 * If we have a graft pending, cancel graft retransmission
427 for (i = 0; i < 4; i++)
428 *p++ = ((char *)&(gt->gt_route->rt_origin))[i];
429 for (i = 0; i < 4; i++)
430 *p++ = ((char *)&(gt->gt_mcastgrp))[i];
431 tmp = htonl(gt->gt_prsent_timer);
432 for (i = 0; i < 4; i++)
433 *p++ = ((char *)&(tmp))[i];
436 send_on_vif(v, dst, DVMRP_PRUNE, datalen);
438 IF_DEBUG(DEBUG_PRUNE)
439 log(LOG_DEBUG, 0, "%s prune for (%s %s)/%d on vif %d to %s",
440 rexmitting ? "rexmitted" : "sent",
441 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
442 gt->gt_prsent_timer, gt->gt_route->rt_parent,
443 inet_fmt(gt->gt_route->rt_gateway, s3));
445 if ((v->uv_flags & VIFF_REXMIT_PRUNES) &&
446 gt->gt_rexmit_timer == 0 &&
447 gt->gt_prsent_timer > gt->gt_prune_rexmit) {
448 struct gtable **arg =
449 (struct gtable **)malloc(sizeof (struct gtable **));
452 gt->gt_rexmit_timer = timer_setTimer(
453 JITTERED_VALUE(gt->gt_prune_rexmit),
455 gt->gt_prune_rexmit *= 2;
460 * a prune was sent upstream
461 * so, a graft has to be sent to annul the prune
462 * set up a graft timer so that if an ack is not
463 * heard within that time, another graft request
475 /* Can't send a graft without an associated route */
476 if (gt->gt_route == NULL || gt->gt_route->rt_parent == NO_VIF) {
481 gt->gt_prsent_timer = 0;
482 gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
483 if (gt->gt_rexmit_timer)
484 timer_clearTimer(gt->gt_rexmit_timer);
486 if (gt->gt_grftsnt == 0)
490 dst = uvifs[gt->gt_route->rt_parent].uv_flags & VIFF_TUNNEL ? dvmrp_group : gt->gt_route->rt_gateway; /*XXX*/
492 dst = gt->gt_route->rt_gateway;
495 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
498 for (i = 0; i < 4; i++)
499 *p++ = ((char *)&(gt->gt_route->rt_origin))[i];
500 for (i = 0; i < 4; i++)
501 *p++ = ((char *)&(gt->gt_mcastgrp))[i];
504 send_on_vif(&uvifs[gt->gt_route->rt_parent], dst, DVMRP_GRAFT, datalen);
505 IF_DEBUG(DEBUG_PRUNE)
506 log(LOG_DEBUG, 0, "sent graft for (%s %s) to %s on vif %d",
507 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
508 inet_fmt(gt->gt_route->rt_gateway, s3), gt->gt_route->rt_parent);
512 * Send an ack that a graft was received
515 send_graft_ack(src, dst, origin, grp, vifi)
526 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
529 for (i = 0; i < 4; i++)
530 *p++ = ((char *)&(origin))[i];
531 for (i = 0; i < 4; i++)
532 *p++ = ((char *)&(grp))[i];
536 send_igmp(src, dst, IGMP_DVMRP, DVMRP_GRAFT_ACK,
537 htonl(MROUTED_LEVEL), datalen);
540 if (uvifs[vifi].uv_flags & VIFF_TUNNEL)
541 dst = dvmrp_group; /* XXX */
543 send_on_vif(&uvifs[vifi], dst, DVMRP_GRAFT_ACK, datalen);
546 IF_DEBUG(DEBUG_PRUNE)
548 log(LOG_DEBUG, 0, "sent graft ack for (%s, %s) to %s",
549 inet_fmt(origin, s1), inet_fmt(grp, s2), inet_fmt(dst, s3));
551 log(LOG_DEBUG, 0, "sent graft ack for (%s, %s) to %s on vif %d",
552 inet_fmt(origin, s1), inet_fmt(grp, s2), inet_fmt(dst, s3), vifi);
556 * Update the kernel cache with all the routes hanging off the group entry
564 for (st = g->gt_srctbl; st; st = st->st_next)
565 if (st->st_ctime != 0)
566 k_add_rg(st->st_origin, g);
569 /****************************************************************************
570 Functions that are used externally
571 ****************************************************************************/
574 #include <sys/types.h>
578 * Find a specific group entry in the group table
586 for (gt = kernel_table; gt; gt = gt->gt_gnext) {
587 if (ntohl(grp) < ntohl(gt->gt_mcastgrp))
589 if (gt->gt_mcastgrp == grp)
596 * Given a group entry and source, find the corresponding source table
600 find_grp_src(gt, src)
605 u_long grp = gt->gt_mcastgrp;
606 struct gtable *gtcurr;
608 for (gtcurr = gt; gtcurr->gt_mcastgrp == grp; gtcurr = gtcurr->gt_gnext) {
609 for (st = gtcurr->gt_srctbl; st; st = st->st_next)
610 if (st->st_origin == src)
617 * Find next entry > specification
620 next_grp_src_mask(gtpp, stpp, grp, src, mask)
621 struct gtable **gtpp; /* ordered by group */
622 struct stable **stpp; /* ordered by source */
627 struct gtable *gt, *gbest = NULL;
628 struct stable *st, *sbest = NULL;
630 /* Find first group entry >= grp spec */
631 (*gtpp) = kernel_table;
632 while ((*gtpp) && ntohl((*gtpp)->gt_mcastgrp) < ntohl(grp))
633 (*gtpp)=(*gtpp)->gt_gnext;
635 return 0; /* no more groups */
637 for (gt = kernel_table; gt; gt=gt->gt_gnext) {
638 /* Since grps are ordered, we can stop when group changes from gbest */
639 if (gbest && gbest->gt_mcastgrp != gt->gt_mcastgrp)
641 for (st = gt->gt_srctbl; st; st=st->st_next) {
643 /* Among those entries > spec, find "lowest" one */
644 if (((ntohl(gt->gt_mcastgrp)> ntohl(grp))
645 || (ntohl(gt->gt_mcastgrp)==ntohl(grp)
646 && ntohl(st->st_origin)> ntohl(src))
647 || (ntohl(gt->gt_mcastgrp)==ntohl(grp)
648 && ntohl(st->st_origin)==src && 0xFFFFFFFF>ntohl(mask)))
650 || (ntohl(gt->gt_mcastgrp)< ntohl(gbest->gt_mcastgrp))
651 || (ntohl(gt->gt_mcastgrp)==ntohl(gbest->gt_mcastgrp)
652 && ntohl(st->st_origin)< ntohl(sbest->st_origin)))) {
664 * Ensure that sg contains current information for the given group,source.
665 * This is fetched from the kernel as a unit so that counts for the entry
666 * are consistent, i.e. packet and byte counts for the same entry are
667 * read at the same time.
670 refresh_sg(sg, gt, st)
671 struct sioc_sg_req *sg;
675 static int lastq = -1;
677 if (quantum != lastq || sg->src.s_addr!=st->st_origin
678 || sg->grp.s_addr!=gt->gt_mcastgrp) {
680 sg->src.s_addr = st->st_origin;
681 sg->grp.s_addr = gt->gt_mcastgrp;
682 ioctl(udp_socket, SIOCGETSGCNT, (char *)sg);
687 * Given a routing table entry, and a vifi, find the next entry
688 * equal to or greater than those
691 next_child(gtpp, stpp, grp, src, mask, vifi)
692 struct gtable **gtpp;
693 struct stable **stpp;
697 vifi_t *vifi; /* vif at which to start looking */
699 /* Get (G,S,M) entry */
701 || !((*gtpp) = find_grp(grp))
702 || !((*stpp) = find_grp_src((*gtpp),src)))
703 if (!next_grp_src_mask(gtpp, stpp, grp, src, mask))
706 /* Continue until we get one with a valid next vif */
708 for (; (*gtpp)->gt_route->rt_children && *vifi<numvifs; (*vifi)++)
709 if (VIFM_ISSET(*vifi, (*gtpp)->gt_route->rt_children))
712 } while (next_grp_src_mask(gtpp, stpp, (*gtpp)->gt_mcastgrp,
713 (*stpp)->st_origin, 0xFFFFFFFF) );
720 * Initialize the kernel table structure
726 kernel_no_route = NULL;
731 * Add a new table entry for (origin, mcastgrp)
734 add_table_entry(origin, mcastgrp)
739 struct gtable *gt,**gtnp,*prev_gt;
740 struct stable *st,**stnp;
743 * Since we have to enable mrouting to get the version number,
744 * some cache creation requests can sneak through. Ignore them
745 * since we're not going to do useful stuff until we've performed
746 * final initialization.
752 md_log(MD_MISS, origin, mcastgrp);
755 r = determine_route(origin);
759 * Look for it on the no_route table; if it is found then
760 * it will be detected as a duplicate below.
762 for (gt = kernel_no_route; gt; gt = gt->gt_next)
763 if (mcastgrp == gt->gt_mcastgrp &&
764 gt->gt_srctbl && gt->gt_srctbl->st_origin == origin)
766 gtnp = &kernel_no_route;
768 gtnp = &r->rt_groups;
769 while ((gt = *gtnp) != NULL) {
770 if (gt->gt_mcastgrp >= mcastgrp)
777 if (gt == NULL || gt->gt_mcastgrp != mcastgrp) {
778 gt = (struct gtable *)malloc(sizeof(struct gtable));
780 log(LOG_ERR, 0, "ran out of memory");
782 gt->gt_mcastgrp = mcastgrp;
783 gt->gt_timer = CACHE_LIFETIME(cache_lifetime);
785 gt->gt_prsent_timer = 0;
787 gt->gt_srctbl = NULL;
788 gt->gt_pruntbl = NULL;
790 gt->gt_rexmit_timer = 0;
791 NBRM_CLRALL(gt->gt_prunes);
792 gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
794 gt->gt_rsrr_cache = NULL;
797 /* Calculate forwarding vifs */
798 determine_forwvifs(gt);
806 gt->gt_next->gt_prev = gt;
807 gt->gt_prev = prev_gt;
810 if (find_src_grp(r->rt_origin, r->rt_originmask, gt->gt_mcastgrp)) {
813 g = gtp ? gtp->gt_gnext : kernel_table;
814 log(LOG_WARNING, 0, "Entry for (%s %s) (rt:%x) exists (rt:%x)",
815 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
819 gt->gt_gnext = gtp->gt_gnext;
823 gt->gt_gnext = kernel_table;
828 gt->gt_gnext->gt_gprev = gt;
831 gt->gt_gnext = gt->gt_gprev = NULL;
835 stnp = >->gt_srctbl;
836 while ((st = *stnp) != NULL) {
837 if (ntohl(st->st_origin) >= ntohl(origin))
842 if (st == NULL || st->st_origin != origin) {
843 st = (struct stable *)malloc(sizeof(struct stable));
845 log(LOG_ERR, 0, "ran out of memory");
847 st->st_origin = origin;
854 if (st->st_ctime == 0) {
855 /* An old source which we're keeping around for statistics */
859 md_log(MD_DUPE, origin, mcastgrp);
861 /* Ignore kernel->mrouted retransmissions */
862 if (time(0) - st->st_ctime > 5)
863 log(LOG_WARNING, 0, "kernel entry already exists for (%s %s)",
864 inet_fmt(origin, s1), inet_fmt(mcastgrp, s2));
865 k_add_rg(origin, gt);
871 k_add_rg(origin, gt);
873 IF_DEBUG(DEBUG_CACHE)
874 log(LOG_DEBUG, 0, "add cache entry (%s %s) gm:%x, parent-vif:%d",
875 inet_fmt(origin, s1),
876 inet_fmt(mcastgrp, s2),
877 gt->gt_grpmems, r ? r->rt_parent : -1);
880 * If there are no downstream routers that want traffic for
881 * this group, send (or retransmit) a prune upstream.
883 if (VIFM_ISEMPTY(gt->gt_grpmems))
888 * A router has gone down. Remove prune state pertinent to that router.
891 reset_neighbor_state(vifi, addr)
897 struct ptable *pt, **ptnp;
900 for (g = kernel_table; g; g = g->gt_gnext) {
904 * If neighbor was the parent, remove the prune sent state
905 * and all of the source cache info so that prunes get
908 if (vifi == r->rt_parent) {
909 if (addr == r->rt_gateway) {
911 log(LOG_DEBUG, 0, "reset_neighbor_state parent reset (%s %s)",
912 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
914 g->gt_prsent_timer = 0;
916 while ((st = g->gt_srctbl) != NULL) {
917 g->gt_srctbl = st->st_next;
918 if (st->st_ctime != 0) {
919 k_del_rg(st->st_origin, g);
927 * Remove any prunes that this router has sent us.
929 ptnp = &g->gt_pruntbl;
930 while ((pt = *ptnp) != NULL) {
931 if (pt->pt_vifi == vifi && pt->pt_router == addr) {
932 NBRM_CLR(pt->pt_index, g->gt_prunes);
940 * And see if we want to forward again.
942 if (!VIFM_ISSET(vifi, g->gt_grpmems)) {
943 GET_MEMBERSHIP(g, vifi);
947 /* Update kernel state */
950 /* Send route change notification to reservation protocol. */
951 rsrr_cache_send(g,1);
955 * If removing this prune causes us to start forwarding
956 * (e.g. the neighbor rebooted), and we sent a prune upstream,
957 * send a graft to cancel the prune.
959 if (!VIFM_ISEMPTY(g->gt_grpmems) && g->gt_prsent_timer)
963 log(LOG_DEBUG, 0, "reset neighbor state (%s %s) gm:%x",
965 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
972 * Delete table entry from the kernel
973 * del_flag determines how many entries to delete
976 del_table_entry(r, mcastgrp, del_flag)
981 struct gtable *g, *prev_g;
982 struct stable *st, *prev_st;
983 struct ptable *pt, *prev_pt;
985 if (del_flag == DEL_ALL_ROUTES) {
988 IF_DEBUG(DEBUG_CACHE)
989 log(LOG_DEBUG, 0, "del_table_entry deleting (%s %s)",
990 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
993 if (st->st_ctime != 0) {
994 if (k_del_rg(st->st_origin, g) < 0) {
995 log(LOG_WARNING, errno,
996 "del_table_entry trying to delete (%s, %s)",
997 inet_fmt(st->st_origin, s1),
998 inet_fmt(g->gt_mcastgrp, s2));
1006 g->gt_srctbl = NULL;
1014 g->gt_pruntbl = NULL;
1017 g->gt_gnext->gt_gprev = g->gt_gprev;
1019 g->gt_gprev->gt_gnext = g->gt_gnext;
1021 kernel_table = g->gt_gnext;
1024 /* Send route change notification to reservation protocol. */
1025 rsrr_cache_send(g,0);
1026 rsrr_cache_clean(g);
1028 if (g->gt_rexmit_timer)
1029 timer_clearTimer(g->gt_rexmit_timer);
1035 r->rt_groups = NULL;
1039 * Dummy routine - someday this may be needed, so it is just there
1041 if (del_flag == DEL_RTE_GROUP) {
1042 prev_g = (struct gtable *)&r->rt_groups;
1043 for (g = r->rt_groups; g; g = g->gt_next) {
1044 if (g->gt_mcastgrp == mcastgrp) {
1045 IF_DEBUG(DEBUG_CACHE)
1046 log(LOG_DEBUG, 0, "del_table_entry deleting (%s %s)",
1047 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
1050 if (st->st_ctime != 0) {
1051 if (k_del_rg(st->st_origin, g) < 0) {
1052 log(LOG_WARNING, errno,
1053 "del_table_entry trying to delete (%s, %s)",
1054 inet_fmt(st->st_origin, s1),
1055 inet_fmt(g->gt_mcastgrp, s2));
1063 g->gt_srctbl = NULL;
1071 g->gt_pruntbl = NULL;
1074 g->gt_gnext->gt_gprev = g->gt_gprev;
1076 g->gt_gprev->gt_gnext = g->gt_gnext;
1078 kernel_table = g->gt_gnext;
1080 if (prev_g != (struct gtable *)&r->rt_groups)
1081 g->gt_next->gt_prev = prev_g;
1083 g->gt_next->gt_prev = NULL;
1084 prev_g->gt_next = g->gt_next;
1086 if (g->gt_rexmit_timer)
1087 timer_clearTimer(g->gt_rexmit_timer);
1089 /* Send route change notification to reservation protocol. */
1090 rsrr_cache_send(g,0);
1091 rsrr_cache_clean(g);
1103 * update kernel table entry when a route entry changes
1106 update_table_entry(r, old_parent_gw)
1108 u_int32 old_parent_gw;
1111 struct ptable *pt, **ptnp;
1113 for (g = r->rt_groups; g; g = g->gt_next) {
1114 ptnp = &g->gt_pruntbl;
1116 * Delete prune entries from non-children, or non-subordinates.
1118 while ((pt = *ptnp)) {
1119 if (!VIFM_ISSET(pt->pt_vifi, r->rt_children) ||
1120 !NBRM_ISSET(pt->pt_index, r->rt_subordinates)) {
1122 IF_DEBUG(DEBUG_PRUNE)
1123 log(LOG_DEBUG, 0, "update_table_entry deleting prune for (%s %s) from %s on vif %d -%s%s",
1124 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1125 inet_fmt(pt->pt_router, s3), pt->pt_vifi,
1126 VIFM_ISSET(pt->pt_vifi, r->rt_children) ? "" : " not a child",
1127 NBRM_ISSET(pt->pt_index, r->rt_subordinates) ? "" : " not a subordinate");
1129 if (!NBRM_ISSET(pt->pt_index, g->gt_prunes)) {
1131 "gt_prunes lost track of (%s %s) from %s on vif %d",
1132 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1133 inet_fmt(pt->pt_router, s3), pt->pt_vifi);
1136 NBRM_CLR(pt->pt_index, g->gt_prunes);
1137 *ptnp = pt->pt_next;
1141 ptnp = &((*ptnp)->pt_next);
1144 IF_DEBUG(DEBUG_CACHE)
1145 log(LOG_DEBUG, 0, "updating cache entries (%s %s) old gm:%x",
1146 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1150 * Forget about a prune or graft that we sent previously if we
1151 * have a new parent router (since the new parent router will
1152 * know nothing about what I sent to the previous parent). The
1153 * old parent will forget any prune state it is keeping for us.
1155 if (old_parent_gw != r->rt_gateway) {
1156 g->gt_prsent_timer = 0;
1160 /* Recalculate membership */
1161 determine_forwvifs(g);
1162 /* send a prune or graft if needed. */
1163 send_prune_or_graft(g);
1165 IF_DEBUG(DEBUG_CACHE)
1166 log(LOG_DEBUG, 0, "updating cache entries (%s %s) new gm:%x",
1167 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1170 /* update ttls and add entry into kernel */
1174 /* Send route change notification to reservation protocol. */
1175 rsrr_cache_send(g,1);
1181 * set the forwarding flag for all mcastgrps on this vifi
1184 update_lclgrp(vifi, mcastgrp)
1191 IF_DEBUG(DEBUG_MEMBER)
1192 log(LOG_DEBUG, 0, "group %s joined on vif %d",
1193 inet_fmt(mcastgrp, s1), vifi);
1195 for (g = kernel_table; g; g = g->gt_gnext) {
1196 if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1200 if (g->gt_mcastgrp == mcastgrp &&
1201 VIFM_ISSET(vifi, r->rt_children)) {
1203 VIFM_SET(vifi, g->gt_grpmems);
1205 if (VIFM_ISEMPTY(g->gt_grpmems))
1209 IF_DEBUG(DEBUG_CACHE)
1210 log(LOG_DEBUG, 0, "update lclgrp (%s %s) gm:%x",
1212 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1216 /* Send route change notification to reservation protocol. */
1217 rsrr_cache_send(g,1);
1224 * reset forwarding flag for all mcastgrps on this vifi
1227 delete_lclgrp(vifi, mcastgrp)
1233 IF_DEBUG(DEBUG_MEMBER)
1234 log(LOG_DEBUG, 0, "group %s left on vif %d",
1235 inet_fmt(mcastgrp, s1), vifi);
1237 for (g = kernel_table; g; g = g->gt_gnext) {
1238 if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1241 if (g->gt_mcastgrp == mcastgrp && VIFM_ISSET(vifi, g->gt_grpmems)) {
1242 if (g->gt_route == NULL ||
1243 SUBS_ARE_PRUNED(g->gt_route->rt_subordinates,
1244 uvifs[vifi].uv_nbrmap, g->gt_prunes)) {
1245 VIFM_CLR(vifi, g->gt_grpmems);
1246 IF_DEBUG(DEBUG_CACHE)
1247 log(LOG_DEBUG, 0, "delete lclgrp (%s %s) gm:%x",
1248 RT_FMT(g->gt_route, s1),
1249 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1254 /* Send route change notification to reservation protocol. */
1255 rsrr_cache_send(g,1);
1259 * If there are no more members of this particular group,
1260 * send prune upstream
1262 if (VIFM_ISEMPTY(g->gt_grpmems) && g->gt_route->rt_gateway)
1270 * Takes the prune message received and then strips it to
1271 * determine the (src, grp) pair to be pruned.
1273 * Adds the router to the (src, grp) entry then.
1275 * Determines if further packets have to be sent down that vif
1277 * Determines if a corresponding prune message has to be generated
1280 accept_prune(src, dst, p, datalen)
1295 if ((vifi = find_vif(src, dst)) == NO_VIF) {
1297 "ignoring prune report from non-neighbor %s",
1302 /* Check if enough data is present */
1306 "non-decipherable prune from %s",
1311 for (i = 0; i< 4; i++)
1312 ((char *)&prun_src)[i] = *p++;
1313 for (i = 0; i< 4; i++)
1314 ((char *)&prun_grp)[i] = *p++;
1315 for (i = 0; i< 4; i++)
1316 ((char *)&prun_tmr)[i] = *p++;
1317 prun_tmr = ntohl(prun_tmr);
1319 if (prun_tmr <= MIN_PRUNE_LIFE) {
1320 IF_DEBUG(DEBUG_PRUNE)
1321 log(LOG_DEBUG, 0, "ignoring prune from %s on vif %d for (%s %s)/%d because its lifetime is too short",
1322 inet_fmt(src, s1), vifi,
1323 inet_fmt(prun_src, s2), inet_fmt(prun_grp, s3), prun_tmr);
1327 IF_DEBUG(DEBUG_PRUNE)
1328 log(LOG_DEBUG, 0, "%s on vif %d prunes (%s %s)/%d",
1329 inet_fmt(src, s1), vifi,
1330 inet_fmt(prun_src, s2), inet_fmt(prun_grp, s3), prun_tmr);
1333 * Find the subnet for the prune
1335 if (find_src_grp(prun_src, 0, prun_grp)) {
1336 g = gtp ? gtp->gt_gnext : kernel_table;
1339 IF_DEBUG(DEBUG_PRUNE)
1340 log(LOG_DEBUG, 0, "found grp state, (%s %s), metric is %d, children are %x, subords are %08x%08x",
1341 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2), r->rt_metric,
1342 r->rt_children, r->rt_subordinates.hi, r->rt_subordinates.lo);
1343 if (!VIFM_ISSET(vifi, r->rt_children)) {
1344 IF_DEBUG(DEBUG_PRUNE)
1345 log(LOG_WARNING, 0, "prune received from non-child %s for (%s %s) (dominant on vif %d is %s)",
1346 inet_fmt(src, s1), inet_fmt(prun_src, s2),
1347 inet_fmt(prun_grp, s3), vifi,
1348 inet_fmt(r->rt_dominants[vifi], s4));
1354 if (VIFM_ISSET(vifi, g->gt_scope)) {
1355 log(LOG_WARNING, 0, "prune received from %s on scoped grp (%s %s)",
1356 inet_fmt(src, s1), inet_fmt(prun_src, s2),
1357 inet_fmt(prun_grp, s3));
1360 if ((pt = find_prune_entry(src, g->gt_pruntbl)) != NULL) {
1361 IF_DEBUG(DEBUG_PRUNE)
1362 log(LOG_DEBUG, 0, "%s %d from %s for (%s %s)/%d %s %d %s %x",
1363 "duplicate prune received on vif",
1364 vifi, inet_fmt(src, s1), inet_fmt(prun_src, s2),
1365 inet_fmt(prun_grp, s3), prun_tmr,
1366 "old timer:", pt->pt_timer, "cur gm:", g->gt_grpmems);
1367 pt->pt_timer = prun_tmr;
1369 struct listaddr *n = neighbor_info(vifi, src);
1372 log(LOG_WARNING, 0, "Prune from non-neighbor %s on vif %d!?",
1373 inet_fmt(src, s1), vifi);
1377 /* allocate space for the prune structure */
1378 pt = (struct ptable *)(malloc(sizeof(struct ptable)));
1380 log(LOG_ERR, 0, "pt: ran out of memory");
1383 pt->pt_router = src;
1384 pt->pt_timer = prun_tmr;
1386 pt->pt_next = g->gt_pruntbl;
1390 pt->pt_index = n->al_index;
1391 NBRM_SET(n->al_index, g->gt_prunes);
1396 * check if any more packets need to be sent on the
1397 * vif which sent this message
1399 if (SUBS_ARE_PRUNED(r->rt_subordinates,
1400 uvifs[vifi].uv_nbrmap, g->gt_prunes) &&
1401 !grplst_mem(vifi, prun_grp)) {
1404 VIFM_CLR(vifi, g->gt_grpmems);
1405 IF_DEBUG(DEBUG_PRUNE)
1406 log(LOG_DEBUG, 0, "vifnbrs=0x%08x%08x, subord=0x%08x%08x prunes=0x%08x%08x",
1407 uvifs[vifi].uv_nbrmap.hi,uvifs[vifi].uv_nbrmap.lo,
1408 r->rt_subordinates.hi, r->rt_subordinates.lo,
1409 g->gt_prunes.hi, g->gt_prunes.lo);
1411 NBRM_COPY(r->rt_subordinates, tmp);
1412 NBRM_MASK(tmp, uvifs[vifi].uv_nbrmap);
1413 if (!NBRM_ISSETALLMASK(g->gt_prunes, tmp))
1414 log(LOG_WARNING, 0, "subordinate error");
1415 /* XXX end debugging */
1416 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1417 log(LOG_DEBUG, 0, "prune (%s %s), stop sending on vif %d, gm:%x",
1419 inet_fmt(g->gt_mcastgrp, s2), vifi, g->gt_grpmems);
1424 /* Send route change notification to reservation protocol. */
1425 rsrr_cache_send(g,1);
1430 * check if all the child routers have expressed no interest
1431 * in this group and if this group does not exist in the
1433 * Send a prune message then upstream
1435 if (VIFM_ISEMPTY(g->gt_grpmems) && r->rt_gateway) {
1440 * There is no kernel entry for this group. Therefore, we can
1441 * simply ignore the prune, as we are not forwarding this traffic
1444 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1445 log(LOG_DEBUG, 0, "%s (%s %s)/%d from %s",
1446 "prune message received with no kernel entry for",
1447 inet_fmt(prun_src, s1), inet_fmt(prun_grp, s2),
1448 prun_tmr, inet_fmt(src, s3));
1454 * Checks if this mcastgrp is present in the kernel table
1455 * If so and if a prune was sent, it sends a graft upwards
1458 chkgrp_graft(vifi, mcastgrp)
1465 for (g = kernel_table; g; g = g->gt_gnext) {
1466 if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1470 if (g->gt_mcastgrp == mcastgrp && VIFM_ISSET(vifi, r->rt_children))
1471 if (g->gt_prsent_timer) {
1472 VIFM_SET(vifi, g->gt_grpmems);
1475 * If the vif that was joined was a scoped vif,
1476 * ignore it ; don't graft back
1479 if (VIFM_ISEMPTY(g->gt_grpmems))
1482 /* send graft upwards */
1485 /* update cache timer*/
1486 g->gt_timer = CACHE_LIFETIME(cache_lifetime);
1488 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1489 log(LOG_DEBUG, 0, "chkgrp graft (%s %s) gm:%x",
1491 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1496 /* Send route change notification to reservation protocol. */
1497 rsrr_cache_send(g,1);
1503 /* determine the multicast group and src
1505 * if it does, then determine if a prune was sent
1507 * if prune sent upstream, send graft upstream and send
1510 * if no prune sent upstream, change the forwarding bit
1511 * for this interface and send ack downstream.
1513 * if no entry exists for this group send ack downstream.
1516 accept_graft(src, dst, p, datalen)
1528 struct ptable *pt, **ptnp;
1532 "received non-decipherable graft from %s",
1537 for (i = 0; i< 4; i++)
1538 ((char *)&graft_src)[i] = *p++;
1539 for (i = 0; i< 4; i++)
1540 ((char *)&graft_grp)[i] = *p++;
1542 vifi = find_vif(src, dst);
1543 send_graft_ack(dst, src, graft_src, graft_grp, vifi);
1545 if (vifi == NO_VIF) {
1547 "ignoring graft for (%s %s) from non-neighbor %s",
1548 inet_fmt(graft_src, s2), inet_fmt(graft_grp, s3),
1553 IF_DEBUG(DEBUG_PRUNE)
1554 log(LOG_DEBUG, 0, "%s on vif %d grafts (%s %s)",
1555 inet_fmt(src, s1), vifi,
1556 inet_fmt(graft_src, s2), inet_fmt(graft_grp, s3));
1559 * Find the subnet for the graft
1561 if (find_src_grp(graft_src, 0, graft_grp)) {
1562 g = gtp ? gtp->gt_gnext : kernel_table;
1565 if (VIFM_ISSET(vifi, g->gt_scope)) {
1566 log(LOG_WARNING, 0, "graft received from %s on scoped grp (%s %s)",
1567 inet_fmt(src, s1), inet_fmt(graft_src, s2),
1568 inet_fmt(graft_grp, s3));
1572 ptnp = &g->gt_pruntbl;
1573 while ((pt = *ptnp) != NULL) {
1574 if ((pt->pt_vifi == vifi) && (pt->pt_router == src)) {
1575 NBRM_CLR(pt->pt_index, g->gt_prunes);
1576 *ptnp = pt->pt_next;
1579 VIFM_SET(vifi, g->gt_grpmems);
1580 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1581 log(LOG_DEBUG, 0, "accept graft (%s %s) gm:%x",
1583 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1588 /* Send route change notification to reservation protocol. */
1589 rsrr_cache_send(g,1);
1593 ptnp = &pt->pt_next;
1597 g->gt_timer = CACHE_LIFETIME(cache_lifetime);
1599 if (g->gt_prsent_timer)
1600 /* send graft upwards */
1604 * We have no state for the source and group in question.
1605 * This is fine, since we know that we have no prune state, and
1606 * grafts are requests to remove prune state.
1608 IF_DEBUG(DEBUG_PRUNE)
1609 log(LOG_DEBUG, 0, "%s (%s %s) from %s",
1610 "graft received with no kernel entry for",
1611 inet_fmt(graft_src, s1), inet_fmt(graft_grp, s2),
1618 * find out which group is involved first of all
1619 * then determine if a graft was sent.
1620 * if no graft sent, ignore the message
1621 * if graft was sent and the ack is from the right
1622 * source, remove the graft timer so that we don't
1623 * have send a graft again
1626 accept_g_ack(src, dst, p, datalen)
1638 if ((vifi = find_vif(src, dst)) == NO_VIF) {
1640 "ignoring graft ack from non-neighbor %s",
1645 if (datalen < 0 || datalen > 8) {
1647 "received non-decipherable graft ack from %s",
1652 for (i = 0; i< 4; i++)
1653 ((char *)&grft_src)[i] = *p++;
1654 for (i = 0; i< 4; i++)
1655 ((char *)&grft_grp)[i] = *p++;
1657 IF_DEBUG(DEBUG_PRUNE)
1658 log(LOG_DEBUG, 0, "%s on vif %d acks graft (%s, %s)",
1659 inet_fmt(src, s1), vifi,
1660 inet_fmt(grft_src, s2), inet_fmt(grft_grp, s3));
1663 * Find the subnet for the graft ack
1665 if (find_src_grp(grft_src, 0, grft_grp)) {
1666 g = gtp ? gtp->gt_gnext : kernel_table;
1669 log(LOG_WARNING, 0, "%s (%s, %s) from %s",
1670 "rcvd graft ack with no kernel entry for",
1671 inet_fmt(grft_src, s1), inet_fmt(grft_grp, s2),
1682 * free all prune entries and kernel routes
1683 * normally, this should inform the kernel that all of its routes
1684 * are going away, but this is only called by restart(), which is
1685 * about to call MRT_DONE which does that anyway.
1690 register struct rtentry *r;
1691 register struct gtable *g, *prev_g;
1692 register struct stable *s, *prev_s;
1693 register struct ptable *p, *prev_p;
1695 for (r = routing_table; r; r = r->rt_next) {
1714 if (prev_g->gt_rexmit_timer)
1715 timer_clearTimer(prev_g->gt_rexmit_timer);
1718 r->rt_groups = NULL;
1720 kernel_table = NULL;
1722 g = kernel_no_route;
1729 if (prev_g->gt_rexmit_timer)
1730 timer_clearTimer(prev_g->gt_rexmit_timer);
1733 kernel_no_route = NULL;
1737 * When a new route is created, search
1738 * a) The less-specific part of the routing table
1739 * b) The route-less kernel table
1740 * for sources that the new route might want to handle.
1742 * "Inheriting" these sources might be cleanest, but simply deleting
1743 * them is easier, and letting the kernel re-request them.
1749 register struct rtentry *rp;
1750 register struct gtable *gt, **gtnp;
1751 register struct stable *st, **stnp;
1753 for (rp = rt->rt_next; rp; rp = rp->rt_next) {
1754 if (rp->rt_groups == NULL)
1756 if ((rt->rt_origin & rp->rt_originmask) == rp->rt_origin) {
1757 IF_DEBUG(DEBUG_ROUTE)
1758 log(LOG_DEBUG, 0, "Route for %s stealing sources from %s",
1759 RT_FMT(rt, s1), RT_FMT(rp, s2));
1760 for (gt = rp->rt_groups; gt; gt = gt->gt_next) {
1761 stnp = >->gt_srctbl;
1762 while ((st = *stnp) != NULL) {
1763 if ((st->st_origin & rt->rt_originmask) == rt->rt_origin) {
1764 IF_DEBUG(DEBUG_ROUTE)
1765 log(LOG_DEBUG, 0, "%s stealing (%s %s) from %s",
1767 inet_fmt(st->st_origin, s3),
1768 inet_fmt(gt->gt_mcastgrp, s4),
1770 if (st->st_ctime != 0) {
1771 if (k_del_rg(st->st_origin, gt) < 0) {
1772 log(LOG_WARNING, errno, "%s (%s, %s)",
1773 "steal_sources trying to delete",
1774 inet_fmt(st->st_origin, s1),
1775 inet_fmt(gt->gt_mcastgrp, s2));
1779 *stnp = st->st_next;
1782 stnp = &st->st_next;
1789 gtnp = &kernel_no_route;
1790 while ((gt = *gtnp) != NULL) {
1791 if (gt->gt_srctbl && ((gt->gt_srctbl->st_origin & rt->rt_originmask)
1792 == rt->rt_origin)) {
1793 IF_DEBUG(DEBUG_ROUTE)
1794 log(LOG_DEBUG, 0, "%s stealing (%s %s) from %s",
1796 inet_fmt(gt->gt_srctbl->st_origin, s3),
1797 inet_fmt(gt->gt_mcastgrp, s4),
1799 if (gt->gt_srctbl->st_ctime != 0) {
1800 if (k_del_rg(gt->gt_srctbl->st_origin, gt) < 0) {
1801 log(LOG_WARNING, errno, "%s (%s %s)",
1802 "steal_sources trying to delete",
1803 inet_fmt(gt->gt_srctbl->st_origin, s1),
1804 inet_fmt(gt->gt_mcastgrp, s2));
1808 free(gt->gt_srctbl);
1809 *gtnp = gt->gt_next;
1811 gt->gt_next->gt_prev = gt->gt_prev;
1812 if (gt->gt_rexmit_timer)
1813 timer_clearTimer(gt->gt_rexmit_timer);
1816 gtnp = >->gt_next;
1822 * Advance the timers on all the cache entries.
1823 * If there are any entries whose timers have expired,
1824 * remove these entries from the kernel cache.
1830 struct gtable *gt, **gtnptr;
1831 struct stable *st, **stnp;
1832 struct ptable *pt, **ptnp;
1833 struct sioc_sg_req sg_req;
1835 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1836 log(LOG_DEBUG, 0, "aging forwarding cache entries");
1838 gtnptr = &kernel_table;
1839 while ((gt = *gtnptr) != NULL) {
1840 vifi_t i; /* XXX Debugging */
1841 int fixit = 0; /* XXX Debugging */
1845 /* XXX Debugging... */
1846 for (i = 0; i < numvifs; i++) {
1848 * If we're not sending on this vif,
1849 * And this group isn't scoped on this vif,
1850 * And I'm the parent for this route on this vif,
1851 * And there are subordinates on this vif,
1852 * And all of the subordinates haven't pruned,
1854 * and remember to fix it up later
1856 if (!VIFM_ISSET(i, gt->gt_grpmems) &&
1857 !VIFM_ISSET(i, gt->gt_scope) &&
1858 VIFM_ISSET(i, r->rt_children) &&
1859 NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates) &&
1860 !SUBS_ARE_PRUNED(r->rt_subordinates, uvifs[i].uv_nbrmap, gt->gt_prunes)) {
1861 log(LOG_WARNING, 0, "(%s %s) is blackholing on vif %d",
1862 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), i);
1867 log(LOG_WARNING, 0, "fixing membership for (%s %s) gm:%x",
1868 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems);
1869 determine_forwvifs(gt);
1870 send_prune_or_graft(gt);
1871 log(LOG_WARNING, 0, "fixed membership for (%s %s) gm:%x",
1872 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems);
1878 /* If there are group members,
1879 * and there are recent sources,
1880 * and we have a route,
1881 * and it's not directly connected,
1882 * and we haven't sent a prune,
1883 * if there are any cache entries in the kernel
1884 * [if there aren't we're probably waiting to rexmit],
1888 if (VIFM_ISEMPTY(gt->gt_grpmems) && gt->gt_srctbl && r && r->rt_gateway && gt->gt_prsent_timer == 0) {
1889 for (st = gt->gt_srctbl; st; st = st->st_next)
1890 if (st->st_ctime != 0)
1893 log(LOG_WARNING, 0, "grpmems for (%s %s) is empty but no prune state!", RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
1894 send_prune_or_graft(gt);
1900 /* XXX ...Debugging */
1902 /* advance the timer for the kernel entry */
1903 gt->gt_timer -= TIMER_INTERVAL;
1905 /* decrement prune timer if need be */
1906 if (gt->gt_prsent_timer > 0) {
1907 gt->gt_prsent_timer -= TIMER_INTERVAL;
1908 if (gt->gt_prsent_timer <= 0) {
1909 IF_DEBUG(DEBUG_PRUNE)
1910 log(LOG_DEBUG, 0, "upstream prune tmo (%s %s)",
1912 inet_fmt(gt->gt_mcastgrp, s2));
1913 gt->gt_prsent_timer = -1;
1914 /* Reset the prune retransmission timer to its initial value */
1915 gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
1919 /* retransmit graft with exponential backoff */
1920 if (gt->gt_grftsnt) {
1923 y = ++gt->gt_grftsnt;
1924 while (y && !(y & 1))
1933 * If a prune expires, forward again on that vif.
1935 ptnp = >->gt_pruntbl;
1936 while ((pt = *ptnp) != NULL) {
1937 if ((pt->pt_timer -= TIMER_INTERVAL) <= 0) {
1938 IF_DEBUG(DEBUG_PRUNE)
1939 log(LOG_DEBUG, 0, "expire prune (%s %s) from %s on vif %d",
1941 inet_fmt(gt->gt_mcastgrp, s2),
1942 inet_fmt(pt->pt_router, s3),
1944 if (gt->gt_prsent_timer > 0) {
1945 log(LOG_WARNING, 0, "prune (%s %s) from %s on vif %d expires with %d left on prsent timer",
1947 inet_fmt(gt->gt_mcastgrp, s2),
1948 inet_fmt(pt->pt_router, s3),
1949 pt->pt_vifi, gt->gt_prsent_timer);
1950 /* Send a graft to heal the tree. */
1954 NBRM_CLR(pt->pt_index, gt->gt_prunes);
1955 expire_prune(pt->pt_vifi, gt);
1957 /* remove the router's prune entry and await new one */
1958 *ptnp = pt->pt_next;
1961 ptnp = &pt->pt_next;
1966 * If the cache entry has expired, delete source table entries for
1967 * silent sources. If there are no source entries left, and there
1968 * are no downstream prunes, then the entry is deleted.
1969 * Otherwise, the cache entry's timer is refreshed.
1971 if (gt->gt_timer <= 0) {
1972 IF_DEBUG(DEBUG_CACHE)
1973 log(LOG_DEBUG, 0, "(%s %s) timed out, checking for traffic",
1974 RT_FMT(gt->gt_route, s1),
1975 inet_fmt(gt->gt_mcastgrp, s2));
1976 /* Check for traffic before deleting source entries */
1977 sg_req.grp.s_addr = gt->gt_mcastgrp;
1978 stnp = >->gt_srctbl;
1979 while ((st = *stnp) != NULL) {
1981 * Source entries with no ctime are not actually in the
1982 * kernel; they have been removed by rexmit_prune() so
1983 * are safe to remove from the list at this point.
1986 sg_req.src.s_addr = st->st_origin;
1987 if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
1988 log(LOG_WARNING, errno, "%s (%s %s)",
1989 "age_table_entry: SIOCGETSGCNT failing for",
1990 inet_fmt(st->st_origin, s1),
1991 inet_fmt(gt->gt_mcastgrp, s2));
1992 /* Make sure it gets deleted below */
1993 sg_req.pktcnt = st->st_pktcnt;
1996 sg_req.pktcnt = st->st_pktcnt;
1998 if (sg_req.pktcnt == st->st_pktcnt) {
1999 *stnp = st->st_next;
2000 IF_DEBUG(DEBUG_CACHE)
2001 log(LOG_DEBUG, 0, "age_table_entry deleting (%s %s)",
2002 inet_fmt(st->st_origin, s1),
2003 inet_fmt(gt->gt_mcastgrp, s2));
2004 if (st->st_ctime != 0) {
2005 if (k_del_rg(st->st_origin, gt) < 0) {
2006 log(LOG_WARNING, errno,
2007 "age_table_entry trying to delete (%s %s)",
2008 inet_fmt(st->st_origin, s1),
2009 inet_fmt(gt->gt_mcastgrp, s2));
2015 st->st_pktcnt = sg_req.pktcnt;
2016 stnp = &st->st_next;
2021 * Retain the group entry if we have downstream prunes or if
2022 * there is at least one source in the list that still has
2023 * traffic, or if our upstream prune timer or graft
2024 * retransmission timer is running.
2026 if (gt->gt_pruntbl != NULL || gt->gt_srctbl != NULL ||
2027 gt->gt_prsent_timer > 0 || gt->gt_grftsnt > 0) {
2028 IF_DEBUG(DEBUG_CACHE)
2029 log(LOG_DEBUG, 0, "refresh lifetim of cache entry %s%s%s%s(%s, %s)",
2030 gt->gt_pruntbl ? "(dstrm prunes) " : "",
2031 gt->gt_srctbl ? "(trfc flow) " : "",
2032 gt->gt_prsent_timer > 0 ? "(upstrm prune) " : "",
2033 gt->gt_grftsnt > 0 ? "(grft rexmit) " : "",
2035 inet_fmt(gt->gt_mcastgrp, s2));
2036 gt->gt_timer = CACHE_LIFETIME(cache_lifetime);
2037 if (gt->gt_prsent_timer == -1) {
2039 * The upstream prune timed out. Remove any kernel
2042 gt->gt_prsent_timer = 0;
2043 if (gt->gt_pruntbl) {
2044 log(LOG_WARNING, 0, "upstream prune for (%s %s) expires with downstream prunes active",
2045 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
2049 gtnptr = >->gt_gnext;
2053 IF_DEBUG(DEBUG_CACHE)
2054 log(LOG_DEBUG, 0, "timeout cache entry (%s, %s)",
2056 inet_fmt(gt->gt_mcastgrp, s2));
2059 gt->gt_prev->gt_next = gt->gt_next;
2061 gt->gt_route->rt_groups = gt->gt_next;
2063 gt->gt_next->gt_prev = gt->gt_prev;
2066 gt->gt_gprev->gt_gnext = gt->gt_gnext;
2067 gtnptr = >->gt_gprev->gt_gnext;
2069 kernel_table = gt->gt_gnext;
2070 gtnptr = &kernel_table;
2073 gt->gt_gnext->gt_gprev = gt->gt_gprev;
2076 /* Send route change notification to reservation protocol. */
2077 rsrr_cache_send(gt,0);
2078 rsrr_cache_clean(gt);
2080 if (gt->gt_rexmit_timer)
2081 timer_clearTimer(gt->gt_rexmit_timer);
2085 if (gt->gt_prsent_timer == -1) {
2087 * The upstream prune timed out. Remove any kernel
2090 gt->gt_prsent_timer = 0;
2091 if (gt->gt_pruntbl) {
2092 log(LOG_WARNING, 0, "upstream prune for (%s %s) expires with downstream prunes active",
2093 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
2097 gtnptr = >->gt_gnext;
2102 * When traversing the no_route table, the decision is much easier.
2103 * Just delete it if it has timed out.
2105 gtnptr = &kernel_no_route;
2106 while ((gt = *gtnptr) != NULL) {
2107 /* advance the timer for the kernel entry */
2108 gt->gt_timer -= TIMER_INTERVAL;
2110 if (gt->gt_timer < 0) {
2111 if (gt->gt_srctbl) {
2112 if (gt->gt_srctbl->st_ctime != 0) {
2113 if (k_del_rg(gt->gt_srctbl->st_origin, gt) < 0) {
2114 log(LOG_WARNING, errno, "%s (%s %s)",
2115 "age_table_entry trying to delete no-route",
2116 inet_fmt(gt->gt_srctbl->st_origin, s1),
2117 inet_fmt(gt->gt_mcastgrp, s2));
2121 free(gt->gt_srctbl);
2123 *gtnptr = gt->gt_next;
2125 gt->gt_next->gt_prev = gt->gt_prev;
2127 if (gt->gt_rexmit_timer)
2128 timer_clearTimer(gt->gt_rexmit_timer);
2132 gtnptr = >->gt_next;
2138 * Modify the kernel to forward packets when one or multiple prunes that
2139 * were received on the vif given by vifi, for the group given by gt,
2143 expire_prune(vifi, gt)
2148 * No need to send a graft, any prunes that we sent
2149 * will expire before any prunes that we have received.
2150 * However, in the case that we did make a mistake,
2151 * send a graft to compensate.
2153 if (gt->gt_prsent_timer >= MIN_PRUNE_LIFE) {
2154 IF_DEBUG(DEBUG_PRUNE)
2155 log(LOG_DEBUG, 0, "prune expired with %d left on %s",
2156 gt->gt_prsent_timer, "prsent_timer");
2157 gt->gt_prsent_timer = 0;
2161 /* modify the kernel entry to forward packets */
2162 if (!VIFM_ISSET(vifi, gt->gt_grpmems)) {
2163 struct rtentry *rt = gt->gt_route;
2164 VIFM_SET(vifi, gt->gt_grpmems);
2165 IF_DEBUG(DEBUG_CACHE)
2166 log(LOG_DEBUG, 0, "forw again (%s %s) gm:%x vif:%d",
2168 inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems, vifi);
2173 /* Send route change notification to reservation protocol. */
2174 rsrr_cache_send(gt,1);
2180 * Print the contents of the cache table on file 'fp2'.
2186 register struct rtentry *r;
2187 register struct gtable *gt;
2188 register struct stable *st;
2189 register struct ptable *pt;
2192 register time_t thyme = time(0);
2195 "Multicast Routing Cache Table (%d entries)\n%s", kroutes,
2196 " Origin Mcast-group CTmr Age Ptmr Rx IVif Forwvifs\n");
2198 "<(prunesrc:vif[idx]/tmr) prunebitmap\n%s",
2199 ">Source Lifetime SavPkt Pkts Bytes RPFf\n");
2201 for (gt = kernel_no_route; gt; gt = gt->gt_next) {
2202 if (gt->gt_srctbl) {
2203 fprintf(fp2, " %-18s %-15s %-8s %-8s - -1 (no route)\n",
2204 inet_fmts(gt->gt_srctbl->st_origin, 0xffffffff, s1),
2205 inet_fmt(gt->gt_mcastgrp, s2), scaletime(gt->gt_timer),
2206 scaletime(thyme - gt->gt_ctime));
2207 fprintf(fp2, ">%s\n", inet_fmt(gt->gt_srctbl->st_origin, s1));
2211 for (gt = kernel_table; gt; gt = gt->gt_gnext) {
2213 fprintf(fp2, " %-18s %-15s",
2215 inet_fmt(gt->gt_mcastgrp, s2));
2217 fprintf(fp2, " %-8s", scaletime(gt->gt_timer));
2219 fprintf(fp2, " %-8s %-8s ", scaletime(thyme - gt->gt_ctime),
2220 gt->gt_prsent_timer ? scaletime(gt->gt_prsent_timer) :
2223 if (gt->gt_prune_rexmit) {
2224 int i = gt->gt_prune_rexmit;
2227 while (i > PRUNE_REXMIT_VAL) {
2231 if (n == 0 && gt->gt_prsent_timer == 0)
2234 fprintf(fp2, "%2d", n);
2239 fprintf(fp2, " %2u%c%c", r->rt_parent,
2240 gt->gt_prsent_timer ? 'P' :
2241 gt->gt_grftsnt ? 'G' : ' ',
2242 VIFM_ISSET(r->rt_parent, gt->gt_scope) ? 'B' : ' ');
2244 for (i = 0; i < numvifs; ++i) {
2245 if (VIFM_ISSET(i, gt->gt_grpmems))
2246 fprintf(fp2, " %u ", i);
2247 else if (VIFM_ISSET(i, r->rt_children) &&
2248 NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
2249 fprintf(fp2, " %u%c", i,
2250 VIFM_ISSET(i, gt->gt_scope) ? 'b' :
2251 SUBS_ARE_PRUNED(r->rt_subordinates,
2252 uvifs[i].uv_nbrmap, gt->gt_prunes) ? 'p' : '!');
2255 if (gt->gt_pruntbl) {
2258 for (pt = gt->gt_pruntbl; pt; pt = pt->pt_next) {
2259 fprintf(fp2, "%c%s:%d[%d]/%d", c, inet_fmt(pt->pt_router, s1),
2260 pt->pt_vifi, pt->pt_index, pt->pt_timer);
2264 fprintf(fp2, " 0x%08lx%08lx\n",/*XXX*/
2265 gt->gt_prunes.hi, gt->gt_prunes.lo);
2267 for (st = gt->gt_srctbl; st; st = st->st_next) {
2268 fprintf(fp2, ">%-18s %-8s %6ld", inet_fmt(st->st_origin, s1),
2269 st->st_ctime ? scaletime(thyme - st->st_ctime) : "-",
2272 struct sioc_sg_req sg_req;
2274 sg_req.src.s_addr = st->st_origin;
2275 sg_req.grp.s_addr = gt->gt_mcastgrp;
2276 if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
2277 log(LOG_WARNING, errno, "SIOCGETSGCNT on (%s %s)",
2278 inet_fmt(st->st_origin, s1),
2279 inet_fmt(gt->gt_mcastgrp, s2));
2281 fprintf(fp2, " %8ld %8ld %4ld", sg_req.pktcnt,
2282 sg_req.bytecnt, sg_req.wrong_if);
2291 * Traceroute function which returns traceroute replies to the requesting
2292 * router. Also forwards the request to downstream routers.
2295 accept_mtrace(src, dst, group, data, no, datalen)
2300 u_int no; /* promoted u_char */
2306 struct tr_query *qry;
2307 struct tr_resp *resp;
2311 int errcode = TR_NO_ERR;
2314 struct sioc_vif_req v_req;
2315 struct sioc_sg_req sg_req;
2317 /* Remember qid across invocations */
2318 static u_int32 oqid = 0;
2320 /* timestamp the request/response */
2321 gettimeofday(&tp, 0);
2324 * Check if it is a query or a response
2326 if (datalen == QLEN) {
2328 IF_DEBUG(DEBUG_TRACE)
2329 log(LOG_DEBUG, 0, "Initial traceroute query rcvd from %s to %s",
2330 inet_fmt(src, s1), inet_fmt(dst, s2));
2332 else if ((datalen - QLEN) % RLEN == 0) {
2334 IF_DEBUG(DEBUG_TRACE)
2335 log(LOG_DEBUG, 0, "In-transit traceroute query rcvd from %s to %s",
2336 inet_fmt(src, s1), inet_fmt(dst, s2));
2337 if (IN_MULTICAST(ntohl(dst))) {
2338 IF_DEBUG(DEBUG_TRACE)
2339 log(LOG_DEBUG, 0, "Dropping multicast response");
2344 log(LOG_WARNING, 0, "%s from %s to %s",
2345 "Non decipherable traceroute request recieved",
2346 inet_fmt(src, s1), inet_fmt(dst, s2));
2350 qry = (struct tr_query *)data;
2353 * if it is a packet with all reports filled, drop it
2355 if ((rcount = (datalen - QLEN)/RLEN) == no) {
2356 IF_DEBUG(DEBUG_TRACE)
2357 log(LOG_DEBUG, 0, "packet with all reports filled in");
2361 IF_DEBUG(DEBUG_TRACE) {
2362 log(LOG_DEBUG, 0, "s: %s g: %s d: %s ", inet_fmt(qry->tr_src, s1),
2363 inet_fmt(group, s2), inet_fmt(qry->tr_dst, s3));
2364 log(LOG_DEBUG, 0, "rttl: %d rd: %s", qry->tr_rttl,
2365 inet_fmt(qry->tr_raddr, s1));
2366 log(LOG_DEBUG, 0, "rcount:%d, qid:%06x", rcount, qry->tr_qid);
2369 /* determine the routing table entry for this traceroute */
2370 rt = determine_route(qry->tr_src);
2371 IF_DEBUG(DEBUG_TRACE)
2373 log(LOG_DEBUG, 0, "rt parent vif: %d rtr: %s metric: %d",
2374 rt->rt_parent, inet_fmt(rt->rt_gateway, s1), rt->rt_metric);
2375 log(LOG_DEBUG, 0, "rt origin %s",
2378 log(LOG_DEBUG, 0, "...no route");
2381 * Query type packet - check if rte exists
2382 * Check if the query destination is a vif connected to me.
2383 * and if so, whether I should start response back
2385 if (type == QUERY) {
2386 if (oqid == qry->tr_qid) {
2388 * If the multicast router is a member of the group being
2389 * queried, and the query is multicasted, then the router can
2390 * recieve multiple copies of the same query. If we have already
2391 * replied to this traceroute, just ignore it this time.
2393 * This is not a total solution, but since if this fails you
2394 * only get N copies, N <= the number of interfaces on the router,
2397 IF_DEBUG(DEBUG_TRACE)
2398 log(LOG_DEBUG, 0, "ignoring duplicate traceroute packet");
2403 IF_DEBUG(DEBUG_TRACE)
2404 log(LOG_DEBUG, 0, "Mcast traceroute: no route entry %s",
2405 inet_fmt(qry->tr_src, s1));
2406 if (IN_MULTICAST(ntohl(dst)))
2409 vifi = find_vif(qry->tr_dst, 0);
2411 if (vifi == NO_VIF) {
2412 /* The traceroute destination is not on one of my subnet vifs. */
2413 IF_DEBUG(DEBUG_TRACE)
2414 log(LOG_DEBUG, 0, "Destination %s not an interface",
2415 inet_fmt(qry->tr_dst, s1));
2416 if (IN_MULTICAST(ntohl(dst)))
2418 errcode = TR_WRONG_IF;
2419 } else if (rt != NULL && !VIFM_ISSET(vifi, rt->rt_children)) {
2420 IF_DEBUG(DEBUG_TRACE)
2421 log(LOG_DEBUG, 0, "Destination %s not on forwarding tree for src %s",
2422 inet_fmt(qry->tr_dst, s1), inet_fmt(qry->tr_src, s2));
2423 if (IN_MULTICAST(ntohl(dst)))
2425 errcode = TR_WRONG_IF;
2430 * determine which interface the packet came in on
2431 * RESP packets travel hop-by-hop so this either traversed
2432 * a tunnel or came from a directly attached mrouter.
2434 if ((vifi = find_vif(src, dst)) == NO_VIF) {
2435 IF_DEBUG(DEBUG_TRACE)
2436 log(LOG_DEBUG, 0, "Wrong interface for packet");
2437 errcode = TR_WRONG_IF;
2441 /* Now that we've decided to send a response, save the qid */
2444 IF_DEBUG(DEBUG_TRACE)
2445 log(LOG_DEBUG, 0, "Sending traceroute response");
2447 /* copy the packet to the sending buffer */
2448 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
2450 bcopy(data, p, datalen);
2455 * If there is no room to insert our reply, coopt the previous hop
2456 * error indication to relay this fact.
2458 if (p + sizeof(struct tr_resp) > send_buf + RECV_BUF_SIZE) {
2459 resp = (struct tr_resp *)p - 1;
2460 resp->tr_rflags = TR_NO_SPACE;
2466 * fill in initial response fields
2468 resp = (struct tr_resp *)p;
2469 bzero(resp, sizeof(struct tr_resp));
2472 resp->tr_qarr = htonl(((tp.tv_sec + JAN_1970) << 16) +
2473 ((tp.tv_usec << 10) / 15625));
2475 resp->tr_rproto = PROTO_DVMRP;
2476 resp->tr_outaddr = (vifi == NO_VIF) ? dst : uvifs[vifi].uv_lcl_addr;
2477 resp->tr_fttl = (vifi == NO_VIF) ? 0 : uvifs[vifi].uv_threshold;
2478 resp->tr_rflags = errcode;
2481 * obtain # of packets out on interface
2484 if (vifi != NO_VIF && ioctl(udp_socket, SIOCGETVIFCNT, (char *)&v_req) >= 0)
2485 resp->tr_vifout = htonl(v_req.ocount);
2487 resp->tr_vifout = 0xffffffff;
2490 * fill in scoping & pruning information
2493 for (gt = rt->rt_groups; gt; gt = gt->gt_next) {
2494 if (gt->gt_mcastgrp >= group)
2500 if (gt && gt->gt_mcastgrp == group) {
2503 for (st = gt->gt_srctbl; st; st = st->st_next)
2504 if (qry->tr_src == st->st_origin)
2507 sg_req.src.s_addr = qry->tr_src;
2508 sg_req.grp.s_addr = group;
2509 if (st && st->st_ctime != 0 &&
2510 ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) >= 0)
2511 resp->tr_pktcnt = htonl(sg_req.pktcnt + st->st_savpkt);
2513 resp->tr_pktcnt = htonl(st ? st->st_savpkt : 0xffffffff);
2515 if (VIFM_ISSET(vifi, gt->gt_scope))
2516 resp->tr_rflags = TR_SCOPED;
2517 else if (gt->gt_prsent_timer)
2518 resp->tr_rflags = TR_PRUNED;
2519 else if (!VIFM_ISSET(vifi, gt->gt_grpmems))
2520 if (!NBRM_ISEMPTY(uvifs[vifi].uv_nbrmap) &&
2521 SUBS_ARE_PRUNED(rt->rt_subordinates,
2522 uvifs[vifi].uv_nbrmap, gt->gt_prunes))
2523 resp->tr_rflags = TR_OPRUNED;
2525 resp->tr_rflags = TR_NO_FWD;
2527 if ((vifi != NO_VIF && scoped_addr(vifi, group)) ||
2528 (rt && scoped_addr(rt->rt_parent, group)))
2529 resp->tr_rflags = TR_SCOPED;
2530 else if (rt && !VIFM_ISSET(vifi, rt->rt_children))
2531 resp->tr_rflags = TR_NO_FWD;
2535 * if no rte exists, set NO_RTE error
2538 src = dst; /* the dst address of resp. pkt */
2539 resp->tr_inaddr = 0;
2540 resp->tr_rflags = TR_NO_RTE;
2541 resp->tr_rmtaddr = 0;
2543 /* get # of packets in on interface */
2544 v_req.vifi = rt->rt_parent;
2545 if (ioctl(udp_socket, SIOCGETVIFCNT, (char *)&v_req) >= 0)
2546 resp->tr_vifin = htonl(v_req.icount);
2548 resp->tr_vifin = 0xffffffff;
2550 MASK_TO_VAL(rt->rt_originmask, resp->tr_smask);
2551 src = uvifs[rt->rt_parent].uv_lcl_addr;
2552 resp->tr_inaddr = src;
2553 resp->tr_rmtaddr = rt->rt_gateway;
2554 if (!VIFM_ISSET(vifi, rt->rt_children)) {
2555 IF_DEBUG(DEBUG_TRACE)
2556 log(LOG_DEBUG, 0, "Destination %s not on forwarding tree for src %s",
2557 inet_fmt(qry->tr_dst, s1), inet_fmt(qry->tr_src, s2));
2558 resp->tr_rflags = TR_WRONG_IF;
2560 if (rt->rt_metric >= UNREACHABLE) {
2561 resp->tr_rflags = TR_NO_RTE;
2562 /* Hack to send reply directly */
2569 * if metric is 1 or no. of reports is 1, send response to requestor
2570 * else send to upstream router. If the upstream router can't handle
2571 * mtrace, set an error code and send to requestor anyway.
2573 IF_DEBUG(DEBUG_TRACE)
2574 log(LOG_DEBUG, 0, "rcount:%d, no:%d", rcount, no);
2576 if ((rcount + 1 == no) || (rt == NULL) || (rt->rt_metric == 1)) {
2577 resptype = IGMP_MTRACE_RESP;
2578 dst = qry->tr_raddr;
2580 if (!can_mtrace(rt->rt_parent, rt->rt_gateway)) {
2581 dst = qry->tr_raddr;
2582 resp->tr_rflags = TR_OLD_ROUTER;
2583 resptype = IGMP_MTRACE_RESP;
2585 dst = rt->rt_gateway;
2586 resptype = IGMP_MTRACE;
2589 if (IN_MULTICAST(ntohl(dst))) {
2591 * Send the reply on a known multicast capable vif.
2592 * If we don't have one, we can't source any multicasts anyway.
2594 if (phys_vif != -1) {
2595 IF_DEBUG(DEBUG_TRACE)
2596 log(LOG_DEBUG, 0, "Sending reply to %s from %s",
2597 inet_fmt(dst, s1), inet_fmt(uvifs[phys_vif].uv_lcl_addr, s2));
2598 k_set_ttl(qry->tr_rttl);
2599 send_igmp(uvifs[phys_vif].uv_lcl_addr, dst,
2600 resptype, no, group,
2604 log(LOG_INFO, 0, "No enabled phyints -- %s",
2605 "dropping traceroute reply");
2607 IF_DEBUG(DEBUG_TRACE)
2608 log(LOG_DEBUG, 0, "Sending %s to %s from %s",
2609 resptype == IGMP_MTRACE_RESP ? "reply" : "request on",
2610 inet_fmt(dst, s1), inet_fmt(src, s2));
2613 resptype, no, group,