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 $
17 extern int cache_lifetime;
18 extern int prune_lifetime;
19 extern struct rtentry *routing_table;
23 extern int allow_black_holes;
26 * randomize value to obtain a value between .5x and 1.5x
27 * in order to prevent synchronization
30 #define JITTERED_VALUE(x) ((x)/2 + (lrand48() % (x)))
32 #define JITTERED_VALUE(x) ((x)/2 + (arc4random() % (x)))
34 #define CACHE_LIFETIME(x) JITTERED_VALUE(x) /* XXX */
36 struct gtable *kernel_table; /* ptr to list of kernel grp entries*/
37 static struct gtable *kernel_no_route; /* list of grp entries w/o routes */
38 struct gtable *gtp; /* pointer for kernel rt entries */
39 unsigned int kroutes; /* current number of cache entries */
41 /****************************************************************************
42 Functions that are local to prune.c
43 ****************************************************************************/
44 static int scoped_addr(vifi_t vifi, u_int32 addr);
45 static void prun_add_ttls(struct gtable *gt);
46 static int pruning_neighbor(vifi_t vifi, u_int32 addr);
47 static int can_mtrace(vifi_t vifi, u_int32 addr);
48 static struct ptable * find_prune_entry(u_int32 vr, struct ptable *pt);
49 static void remove_sources(struct gtable *gt);
50 static void rexmit_prune(void *arg);
51 static void expire_prune(vifi_t vifi, struct gtable *gt);
52 static void send_prune(struct gtable *gt);
53 static void send_graft(struct gtable *gt);
54 static void send_graft_ack(u_int32 src, u_int32 dst,
55 u_int32 origin, u_int32 grp,
57 static void update_kernel(struct gtable *g);
60 * Updates the ttl values for each vif.
63 prun_add_ttls(struct gtable *gt)
68 for (vifi = 0, v = uvifs; vifi < numvifs; ++vifi, ++v) {
69 if (VIFM_ISSET(vifi, gt->gt_grpmems))
70 gt->gt_ttls[vifi] = v->uv_threshold;
72 gt->gt_ttls[vifi] = 0;
77 * checks for scoped multicast addresses
78 * XXX I want to make the check of allow_black_holes based on ALLOW_BLACK_HOLES
79 * but macros are not functions.
81 #define GET_SCOPE(gt) { \
84 VIFM_CLRALL((gt)->gt_scope); \
85 if (allow_black_holes || \
86 (ntohl((gt)->gt_mcastgrp) & 0xff000000) == 0xef000000) \
87 for (_i = 0; _i < numvifs; _i++) \
88 if (scoped_addr(_i, (gt)->gt_mcastgrp)) \
89 VIFM_SET(_i, (gt)->gt_scope); \
91 if ((gt)->gt_route == NULL || ((gt)->gt_route->rt_parent != NO_VIF && \
92 VIFM_ISSET((gt)->gt_route->rt_parent, (gt)->gt_scope))) \
93 VIFM_SETALL((gt)->gt_scope);
95 #define APPLY_SCOPE(gt) VIFM_CLR_MASK((gt)->gt_grpmems, (gt)->gt_scope)
97 #define GET_MEMBERSHIP(gt, vifi) { \
98 if ((gt)->gt_route && \
99 VIFM_ISSET((vifi), (gt)->gt_route->rt_children) && \
100 (!SUBS_ARE_PRUNED((gt)->gt_route->rt_subordinates, \
101 uvifs[vifi].uv_nbrmap, (gt)->gt_prunes) || \
102 grplst_mem((vifi), (gt)->gt_mcastgrp))) \
103 VIFM_SET((vifi), (gt)->gt_grpmems); \
107 scoped_addr(vifi_t vifi, u_int32 addr)
111 for (acl = uvifs[vifi].uv_acl; acl; acl = acl->acl_next)
112 if ((addr & acl->acl_mask) == acl->acl_addr)
119 * Determine the list of outgoing vifs, based upon
120 * route subordinates, prunes received, and group
124 determine_forwvifs(struct gtable *gt)
128 VIFM_CLRALL(gt->gt_grpmems);
129 for (i = 0; i < numvifs; i++) {
130 GET_MEMBERSHIP(gt, i);
137 * Send a prune or a graft if necessary.
140 send_prune_or_graft(struct gtable *gt)
142 if (VIFM_ISEMPTY(gt->gt_grpmems))
144 else if (gt->gt_prsent_timer)
149 * Determine if mcastgrp has a listener on vifi
152 grplst_mem(vifi_t vifi, u_int32 mcastgrp)
159 for (g = v->uv_groups; g != NULL; g = g->al_next)
160 if (mcastgrp == g->al_addr)
167 * Finds the group entry with the specified source and netmask.
168 * If netmask is 0, it uses the route's netmask.
170 * Returns TRUE if found a match, and the global variable gtp is left
171 * pointing to entry before the found entry.
172 * Returns FALSE if no exact match found, gtp is left pointing to before
173 * the entry in question belongs, or is NULL if the it belongs at the
177 find_src_grp(u_int32 src, u_int32 mask, u_int32 grp)
184 if (grp == gt->gt_mcastgrp &&
185 (mask ? (gt->gt_route->rt_origin == src &&
186 gt->gt_route->rt_originmask == mask) :
187 ((src & gt->gt_route->rt_originmask) ==
188 gt->gt_route->rt_origin)))
190 if (ntohl(grp) > ntohl(gt->gt_mcastgrp) ||
191 (grp == gt->gt_mcastgrp &&
192 (ntohl(mask) < ntohl(gt->gt_route->rt_originmask) ||
193 (mask == gt->gt_route->rt_originmask &&
194 (ntohl(src) > ntohl(gt->gt_route->rt_origin)))))) {
204 * Check if the neighbor supports pruning
207 pruning_neighbor(vifi_t vifi, u_int32 addr)
209 struct listaddr *n = neighbor_info(vifi, addr);
216 return (vers >= 0x0300 && ((vers & 0xff00) != 0x0a00));
220 * Can the neighbor in question handle multicast traceroute?
223 can_mtrace(vifi_t vifi, u_int32 addr)
225 struct listaddr *n = neighbor_info(vifi, addr);
229 return 1; /* fail "safe" */
232 return (vers >= 0x0303 && ((vers & 0xff00) != 0x0a00));
236 * Returns the prune entry of the router, or NULL if none exists
238 static struct ptable *
239 find_prune_entry(u_int32 vr, struct ptable *pt)
242 if (pt->pt_router == vr)
251 * Remove all the sources hanging off the group table entry from the kernel
252 * cache. Remember the packet counts wherever possible, to keep the mtrace
253 * counters consistent. This prepares for possible prune retransmission,
254 * either on a multi-access network or when a prune that we sent upstream
258 remove_sources(struct gtable *gt)
261 struct sioc_sg_req sg_req;
263 sg_req.grp.s_addr = gt->gt_mcastgrp;
266 * call k_del_rg() on every one of the gt->gt_srctbl entries
267 * but first save the packet count so that the mtrace packet
268 * counters can remain approximately correct. There's a race
269 * here but it's minor.
271 for (st = gt->gt_srctbl; st; st = st->st_next) {
272 if (st->st_ctime == 0)
274 IF_DEBUG(DEBUG_PRUNE)
275 dolog(LOG_DEBUG, 0, "rexmit_prune deleting (%s %s) (next is %d sec)",
276 inet_fmt(st->st_origin, s1),
277 inet_fmt(gt->gt_mcastgrp, s2),
278 gt->gt_prune_rexmit);
279 sg_req.src.s_addr = st->st_origin;
280 if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
283 k_del_rg(st->st_origin, gt);
284 st->st_ctime = 0; /* flag that it's not in the kernel any more */
285 st->st_savpkt += sg_req.pktcnt;
290 * Now, add_table_entry will prune when asked to add a cache entry.
295 * Prepare for possible prune retransmission
298 rexmit_prune(void *arg)
300 struct gtable *gt = *(struct gtable **)arg;
304 gt->gt_rexmit_timer = 0;
306 /* Make sure we're still not forwarding traffic */
307 if (!VIFM_ISEMPTY(gt->gt_grpmems)) {
308 IF_DEBUG(DEBUG_PRUNE)
309 dolog(LOG_DEBUG, 0, "rexmit_prune (%s %s): gm:%x",
310 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
319 * Send a prune message to the dominant router for
322 * Record an entry that a prune was sent for this group
325 send_prune(struct gtable *gt)
337 * Can't process a prune if we don't have an associated route
338 * or if the route points to a local interface.
340 if (gt->gt_route == NULL || gt->gt_route->rt_parent == NO_VIF ||
341 gt->gt_route->rt_gateway == 0)
344 /* Don't send a prune to a non-pruning router */
345 if (!pruning_neighbor(gt->gt_route->rt_parent, gt->gt_route->rt_gateway))
348 v = &uvifs[gt->gt_route->rt_parent];
350 * sends a prune message to the router upstream.
353 dst = v->uv_flags & VIFF_TUNNEL ? dvmrp_group : gt->gt_route->rt_gateway; /*XXX*/
355 dst = gt->gt_route->rt_gateway;
358 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
362 * determine prune lifetime, if this isn't a retransmission.
364 * Use interface-specified lifetime if there is one.
366 if (gt->gt_prsent_timer == 0) {
367 int l = prune_lifetime;
369 if (v->uv_prune_lifetime != 0)
370 l = v->uv_prune_lifetime;
372 gt->gt_prsent_timer = JITTERED_VALUE(l);
373 for (pt = gt->gt_pruntbl; pt; pt = pt->pt_next)
374 if (pt->pt_timer < gt->gt_prsent_timer)
375 gt->gt_prsent_timer = pt->pt_timer;
376 } else if (gt->gt_prsent_timer < 0) {
377 IF_DEBUG(DEBUG_PRUNE)
378 dolog(LOG_DEBUG, 0, "asked to rexmit? (%s,%s)/%d on vif %d to %s with negative time",
379 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
380 gt->gt_prsent_timer, gt->gt_route->rt_parent,
381 inet_fmt(gt->gt_route->rt_gateway, s3));
386 if (rexmitting && !(v->uv_flags & VIFF_REXMIT_PRUNES)) {
387 IF_DEBUG(DEBUG_PRUNE)
388 dolog(LOG_DEBUG, 0, "not rexmitting prune for (%s %s)/%d on vif %d to %s",
389 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
390 gt->gt_prsent_timer, gt->gt_route->rt_parent,
391 inet_fmt(gt->gt_route->rt_gateway, s3));
394 if (gt->gt_prsent_timer <= MIN_PRUNE_LIFE) {
395 IF_DEBUG(DEBUG_PRUNE)
396 dolog(LOG_DEBUG, 0, "not bothering to send prune for (%s,%s)/%d on vif %d to %s because it's too short",
397 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
398 gt->gt_prsent_timer, gt->gt_route->rt_parent,
399 inet_fmt(gt->gt_route->rt_gateway, s3));
404 * If we have a graft pending, cancel graft retransmission
408 for (i = 0; i < 4; i++)
409 *p++ = ((char *)&(gt->gt_route->rt_origin))[i];
410 for (i = 0; i < 4; i++)
411 *p++ = ((char *)&(gt->gt_mcastgrp))[i];
412 tmp = htonl(gt->gt_prsent_timer);
413 for (i = 0; i < 4; i++)
414 *p++ = ((char *)&(tmp))[i];
417 send_on_vif(v, dst, DVMRP_PRUNE, datalen);
419 IF_DEBUG(DEBUG_PRUNE)
420 dolog(LOG_DEBUG, 0, "%s prune for (%s %s)/%d on vif %d to %s",
421 rexmitting ? "rexmitted" : "sent",
422 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
423 gt->gt_prsent_timer, gt->gt_route->rt_parent,
424 inet_fmt(gt->gt_route->rt_gateway, s3));
426 if ((v->uv_flags & VIFF_REXMIT_PRUNES) &&
427 gt->gt_rexmit_timer == 0 &&
428 gt->gt_prsent_timer > gt->gt_prune_rexmit) {
429 struct gtable **arg =
430 (struct gtable **)malloc(sizeof (struct gtable **));
433 gt->gt_rexmit_timer = timer_setTimer(
434 JITTERED_VALUE(gt->gt_prune_rexmit),
436 gt->gt_prune_rexmit *= 2;
441 * a prune was sent upstream
442 * so, a graft has to be sent to annul the prune
443 * set up a graft timer so that if an ack is not
444 * heard within that time, another graft request
448 send_graft(struct gtable *gt)
455 /* Can't send a graft without an associated route */
456 if (gt->gt_route == NULL || gt->gt_route->rt_parent == NO_VIF) {
461 gt->gt_prsent_timer = 0;
462 gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
463 if (gt->gt_rexmit_timer)
464 timer_clearTimer(gt->gt_rexmit_timer);
466 if (gt->gt_grftsnt == 0)
470 dst = uvifs[gt->gt_route->rt_parent].uv_flags & VIFF_TUNNEL ? dvmrp_group : gt->gt_route->rt_gateway; /*XXX*/
472 dst = gt->gt_route->rt_gateway;
475 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
478 for (i = 0; i < 4; i++)
479 *p++ = ((char *)&(gt->gt_route->rt_origin))[i];
480 for (i = 0; i < 4; i++)
481 *p++ = ((char *)&(gt->gt_mcastgrp))[i];
484 send_on_vif(&uvifs[gt->gt_route->rt_parent], dst, DVMRP_GRAFT, datalen);
485 IF_DEBUG(DEBUG_PRUNE)
486 dolog(LOG_DEBUG, 0, "sent graft for (%s %s) to %s on vif %d",
487 RT_FMT(gt->gt_route, s1), inet_fmt(gt->gt_mcastgrp, s2),
488 inet_fmt(gt->gt_route->rt_gateway, s3), gt->gt_route->rt_parent);
492 * Send an ack that a graft was received
495 send_graft_ack(u_int32 src, u_int32 dst, u_int32 origin, u_int32 grp,
502 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
505 for (i = 0; i < 4; i++)
506 *p++ = ((char *)&(origin))[i];
507 for (i = 0; i < 4; i++)
508 *p++ = ((char *)&(grp))[i];
512 send_igmp(src, dst, IGMP_DVMRP, DVMRP_GRAFT_ACK,
513 htonl(MROUTED_LEVEL), datalen);
516 if (uvifs[vifi].uv_flags & VIFF_TUNNEL)
517 dst = dvmrp_group; /* XXX */
519 send_on_vif(&uvifs[vifi], dst, DVMRP_GRAFT_ACK, datalen);
522 IF_DEBUG(DEBUG_PRUNE)
524 dolog(LOG_DEBUG, 0, "sent graft ack for (%s, %s) to %s",
525 inet_fmt(origin, s1), inet_fmt(grp, s2), inet_fmt(dst, s3));
527 dolog(LOG_DEBUG, 0, "sent graft ack for (%s, %s) to %s on vif %d",
528 inet_fmt(origin, s1), inet_fmt(grp, s2), inet_fmt(dst, s3), vifi);
532 * Update the kernel cache with all the routes hanging off the group entry
535 update_kernel(struct gtable *g)
539 for (st = g->gt_srctbl; st; st = st->st_next)
540 if (st->st_ctime != 0)
541 k_add_rg(st->st_origin, g);
544 /****************************************************************************
545 Functions that are used externally
546 ****************************************************************************/
549 #include <sys/types.h>
553 * Find a specific group entry in the group table
556 find_grp(u_int32 grp)
560 for (gt = kernel_table; gt; gt = gt->gt_gnext) {
561 if (ntohl(grp) < ntohl(gt->gt_mcastgrp))
563 if (gt->gt_mcastgrp == grp)
570 * Given a group entry and source, find the corresponding source table
574 find_grp_src(struct gtable *gt, u_int32 src)
577 u_long grp = gt->gt_mcastgrp;
578 struct gtable *gtcurr;
580 for (gtcurr = gt; gtcurr->gt_mcastgrp == grp; gtcurr = gtcurr->gt_gnext) {
581 for (st = gtcurr->gt_srctbl; st; st = st->st_next)
582 if (st->st_origin == src)
589 * Find next entry > specification
592 next_grp_src_mask(struct gtable **gtpp, /* ordered by group */
593 struct stable **stpp, /* ordered by source */
594 u_int32 grp, u_int32 src, u_int32 mask)
596 struct gtable *gt, *gbest = NULL;
597 struct stable *st, *sbest = NULL;
599 /* Find first group entry >= grp spec */
600 (*gtpp) = kernel_table;
601 while ((*gtpp) && ntohl((*gtpp)->gt_mcastgrp) < ntohl(grp))
602 (*gtpp)=(*gtpp)->gt_gnext;
604 return 0; /* no more groups */
606 for (gt = kernel_table; gt; gt=gt->gt_gnext) {
607 /* Since grps are ordered, we can stop when group changes from gbest */
608 if (gbest && gbest->gt_mcastgrp != gt->gt_mcastgrp)
610 for (st = gt->gt_srctbl; st; st=st->st_next) {
612 /* Among those entries > spec, find "lowest" one */
613 if (((ntohl(gt->gt_mcastgrp)> ntohl(grp))
614 || (ntohl(gt->gt_mcastgrp)==ntohl(grp)
615 && ntohl(st->st_origin)> ntohl(src))
616 || (ntohl(gt->gt_mcastgrp)==ntohl(grp)
617 && ntohl(st->st_origin)==src && 0xFFFFFFFF>ntohl(mask)))
619 || (ntohl(gt->gt_mcastgrp)< ntohl(gbest->gt_mcastgrp))
620 || (ntohl(gt->gt_mcastgrp)==ntohl(gbest->gt_mcastgrp)
621 && ntohl(st->st_origin)< ntohl(sbest->st_origin)))) {
629 return (*gtpp)!=NULL;
633 * Ensure that sg contains current information for the given group,source.
634 * This is fetched from the kernel as a unit so that counts for the entry
635 * are consistent, i.e. packet and byte counts for the same entry are
636 * read at the same time.
639 refresh_sg(struct sioc_sg_req *sg, struct gtable *gt, struct stable *st)
641 static int lastq = -1;
643 if (quantum != lastq || sg->src.s_addr!=st->st_origin
644 || sg->grp.s_addr!=gt->gt_mcastgrp) {
646 sg->src.s_addr = st->st_origin;
647 sg->grp.s_addr = gt->gt_mcastgrp;
648 ioctl(udp_socket, SIOCGETSGCNT, (char *)sg);
653 * Given a routing table entry, and a vifi, find the next entry
654 * equal to or greater than those
657 next_child(struct gtable **gtpp, struct stable **stpp,
658 u_int32 grp, u_int32 src, u_int32 mask,
659 vifi_t vifi) /* vif at which to start looking */
662 /* Get (G,S,M) entry */
664 || !((*gtpp) = find_grp(grp))
665 || !((*stpp) = find_grp_src((*gtpp),src)))
666 if (!next_grp_src_mask(gtpp, stpp, grp, src, mask))
669 /* Continue until we get one with a valid next vif */
671 for (; (*gtpp)->gt_route->rt_children && *vifi<numvifs; (*vifi)++)
672 if (VIFM_ISSET(*vifi, (*gtpp)->gt_route->rt_children))
675 } while (next_grp_src_mask(gtpp, stpp, (*gtpp)->gt_mcastgrp,
676 (*stpp)->st_origin, 0xFFFFFFFF) );
683 * Initialize the kernel table structure
689 kernel_no_route = NULL;
694 * Add a new table entry for (origin, mcastgrp)
697 add_table_entry(u_int32 origin, u_int32 mcastgrp)
700 struct gtable *gt,**gtnp,*prev_gt;
701 struct stable *st,**stnp;
704 * Since we have to enable mrouting to get the version number,
705 * some cache creation requests can sneak through. Ignore them
706 * since we're not going to do useful stuff until we've performed
707 * final initialization.
713 md_log(MD_MISS, origin, mcastgrp);
716 r = determine_route(origin);
720 * Look for it on the no_route table; if it is found then
721 * it will be detected as a duplicate below.
723 for (gt = kernel_no_route; gt; gt = gt->gt_next)
724 if (mcastgrp == gt->gt_mcastgrp &&
725 gt->gt_srctbl && gt->gt_srctbl->st_origin == origin)
727 gtnp = &kernel_no_route;
729 gtnp = &r->rt_groups;
730 while ((gt = *gtnp) != NULL) {
731 if (gt->gt_mcastgrp >= mcastgrp)
738 if (gt == NULL || gt->gt_mcastgrp != mcastgrp) {
739 gt = (struct gtable *)malloc(sizeof(struct gtable));
741 dolog(LOG_ERR, 0, "ran out of memory");
743 gt->gt_mcastgrp = mcastgrp;
744 gt->gt_timer = CACHE_LIFETIME(cache_lifetime);
746 gt->gt_prsent_timer = 0;
748 gt->gt_srctbl = NULL;
749 gt->gt_pruntbl = NULL;
751 gt->gt_rexmit_timer = 0;
752 NBRM_CLRALL(gt->gt_prunes);
753 gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
755 gt->gt_rsrr_cache = NULL;
758 /* Calculate forwarding vifs */
759 determine_forwvifs(gt);
767 gt->gt_next->gt_prev = gt;
768 gt->gt_prev = prev_gt;
771 if (find_src_grp(r->rt_origin, r->rt_originmask, gt->gt_mcastgrp)) {
774 g = gtp ? gtp->gt_gnext : kernel_table;
775 dolog(LOG_WARNING, 0, "Entry for (%s %s) (rt:%x) exists (rt:%x)",
776 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
780 gt->gt_gnext = gtp->gt_gnext;
784 gt->gt_gnext = kernel_table;
789 gt->gt_gnext->gt_gprev = gt;
792 gt->gt_gnext = gt->gt_gprev = NULL;
796 stnp = >->gt_srctbl;
797 while ((st = *stnp) != NULL) {
798 if (ntohl(st->st_origin) >= ntohl(origin))
803 if (st == NULL || st->st_origin != origin) {
804 st = (struct stable *)malloc(sizeof(struct stable));
806 dolog(LOG_ERR, 0, "ran out of memory");
808 st->st_origin = origin;
815 if (st->st_ctime == 0) {
816 /* An old source which we're keeping around for statistics */
820 md_log(MD_DUPE, origin, mcastgrp);
822 /* Ignore kernel->mrouted retransmissions */
823 if (time(0) - st->st_ctime > 5)
824 dolog(LOG_WARNING, 0, "kernel entry already exists for (%s %s)",
825 inet_fmt(origin, s1), inet_fmt(mcastgrp, s2));
826 k_add_rg(origin, gt);
832 k_add_rg(origin, gt);
834 IF_DEBUG(DEBUG_CACHE)
835 dolog(LOG_DEBUG, 0, "add cache entry (%s %s) gm:%x, parent-vif:%d",
836 inet_fmt(origin, s1),
837 inet_fmt(mcastgrp, s2),
838 gt->gt_grpmems, r ? r->rt_parent : -1);
841 * If there are no downstream routers that want traffic for
842 * this group, send (or retransmit) a prune upstream.
844 if (VIFM_ISEMPTY(gt->gt_grpmems))
849 * A router has gone down. Remove prune state pertinent to that router.
852 reset_neighbor_state(vifi_t vifi, u_int32 addr)
856 struct ptable *pt, **ptnp;
859 for (g = kernel_table; g; g = g->gt_gnext) {
863 * If neighbor was the parent, remove the prune sent state
864 * and all of the source cache info so that prunes get
867 if (vifi == r->rt_parent) {
868 if (addr == r->rt_gateway) {
870 dolog(LOG_DEBUG, 0, "reset_neighbor_state parent reset (%s %s)",
871 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
873 g->gt_prsent_timer = 0;
875 while ((st = g->gt_srctbl) != NULL) {
876 g->gt_srctbl = st->st_next;
877 if (st->st_ctime != 0) {
878 k_del_rg(st->st_origin, g);
886 * Remove any prunes that this router has sent us.
888 ptnp = &g->gt_pruntbl;
889 while ((pt = *ptnp) != NULL) {
890 if (pt->pt_vifi == vifi && pt->pt_router == addr) {
891 NBRM_CLR(pt->pt_index, g->gt_prunes);
899 * And see if we want to forward again.
901 if (!VIFM_ISSET(vifi, g->gt_grpmems)) {
902 GET_MEMBERSHIP(g, vifi);
906 /* Update kernel state */
909 /* Send route change notification to reservation protocol. */
910 rsrr_cache_send(g,1);
914 * If removing this prune causes us to start forwarding
915 * (e.g. the neighbor rebooted), and we sent a prune upstream,
916 * send a graft to cancel the prune.
918 if (!VIFM_ISEMPTY(g->gt_grpmems) && g->gt_prsent_timer)
922 dolog(LOG_DEBUG, 0, "reset neighbor state (%s %s) gm:%x",
924 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
931 * Delete table entry from the kernel
932 * del_flag determines how many entries to delete
935 del_table_entry(struct rtentry *r, u_int32 mcastgrp, u_int del_flag)
937 struct gtable *g, *prev_g;
938 struct stable *st, *prev_st;
939 struct ptable *pt, *prev_pt;
941 if (del_flag == DEL_ALL_ROUTES) {
944 IF_DEBUG(DEBUG_CACHE)
945 dolog(LOG_DEBUG, 0, "del_table_entry deleting (%s %s)",
946 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
949 if (st->st_ctime != 0) {
950 if (k_del_rg(st->st_origin, g) < 0) {
951 dolog(LOG_WARNING, errno,
952 "del_table_entry trying to delete (%s, %s)",
953 inet_fmt(st->st_origin, s1),
954 inet_fmt(g->gt_mcastgrp, s2));
970 g->gt_pruntbl = NULL;
973 g->gt_gnext->gt_gprev = g->gt_gprev;
975 g->gt_gprev->gt_gnext = g->gt_gnext;
977 kernel_table = g->gt_gnext;
980 /* Send route change notification to reservation protocol. */
981 rsrr_cache_send(g,0);
984 if (g->gt_rexmit_timer)
985 timer_clearTimer(g->gt_rexmit_timer);
995 * Dummy routine - someday this may be needed, so it is just there
997 if (del_flag == DEL_RTE_GROUP) {
998 prev_g = (struct gtable *)&r->rt_groups;
999 for (g = r->rt_groups; g; g = g->gt_next) {
1000 if (g->gt_mcastgrp == mcastgrp) {
1001 IF_DEBUG(DEBUG_CACHE)
1002 dolog(LOG_DEBUG, 0, "del_table_entry deleting (%s %s)",
1003 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2));
1006 if (st->st_ctime != 0) {
1007 if (k_del_rg(st->st_origin, g) < 0) {
1008 dolog(LOG_WARNING, errno,
1009 "del_table_entry trying to delete (%s, %s)",
1010 inet_fmt(st->st_origin, s1),
1011 inet_fmt(g->gt_mcastgrp, s2));
1019 g->gt_srctbl = NULL;
1027 g->gt_pruntbl = NULL;
1030 g->gt_gnext->gt_gprev = g->gt_gprev;
1032 g->gt_gprev->gt_gnext = g->gt_gnext;
1034 kernel_table = g->gt_gnext;
1036 if (prev_g != (struct gtable *)&r->rt_groups)
1037 g->gt_next->gt_prev = prev_g;
1039 g->gt_next->gt_prev = NULL;
1040 prev_g->gt_next = g->gt_next;
1042 if (g->gt_rexmit_timer)
1043 timer_clearTimer(g->gt_rexmit_timer);
1045 /* Send route change notification to reservation protocol. */
1046 rsrr_cache_send(g,0);
1047 rsrr_cache_clean(g);
1059 * update kernel table entry when a route entry changes
1062 update_table_entry(struct rtentry *r, u_int32 old_parent_gw)
1065 struct ptable *pt, **ptnp;
1067 for (g = r->rt_groups; g; g = g->gt_next) {
1068 ptnp = &g->gt_pruntbl;
1070 * Delete prune entries from non-children, or non-subordinates.
1072 while ((pt = *ptnp)) {
1073 if (!VIFM_ISSET(pt->pt_vifi, r->rt_children) ||
1074 !NBRM_ISSET(pt->pt_index, r->rt_subordinates)) {
1076 IF_DEBUG(DEBUG_PRUNE)
1077 dolog(LOG_DEBUG, 0, "update_table_entry deleting prune for (%s %s) from %s on vif %d -%s%s",
1078 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1079 inet_fmt(pt->pt_router, s3), pt->pt_vifi,
1080 VIFM_ISSET(pt->pt_vifi, r->rt_children) ? "" : " not a child",
1081 NBRM_ISSET(pt->pt_index, r->rt_subordinates) ? "" : " not a subordinate");
1083 if (!NBRM_ISSET(pt->pt_index, g->gt_prunes)) {
1084 dolog(LOG_WARNING, 0,
1085 "gt_prunes lost track of (%s %s) from %s on vif %d",
1086 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1087 inet_fmt(pt->pt_router, s3), pt->pt_vifi);
1090 NBRM_CLR(pt->pt_index, g->gt_prunes);
1091 *ptnp = pt->pt_next;
1095 ptnp = &((*ptnp)->pt_next);
1098 IF_DEBUG(DEBUG_CACHE)
1099 dolog(LOG_DEBUG, 0, "updating cache entries (%s %s) old gm:%x",
1100 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1104 * Forget about a prune or graft that we sent previously if we
1105 * have a new parent router (since the new parent router will
1106 * know nothing about what I sent to the previous parent). The
1107 * old parent will forget any prune state it is keeping for us.
1109 if (old_parent_gw != r->rt_gateway) {
1110 g->gt_prsent_timer = 0;
1114 /* Recalculate membership */
1115 determine_forwvifs(g);
1116 /* send a prune or graft if needed. */
1117 send_prune_or_graft(g);
1119 IF_DEBUG(DEBUG_CACHE)
1120 dolog(LOG_DEBUG, 0, "updating cache entries (%s %s) new gm:%x",
1121 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2),
1124 /* update ttls and add entry into kernel */
1128 /* Send route change notification to reservation protocol. */
1129 rsrr_cache_send(g,1);
1135 * set the forwarding flag for all mcastgrps on this vifi
1138 update_lclgrp(vifi_t vifi, u_int32 mcastgrp)
1143 IF_DEBUG(DEBUG_MEMBER)
1144 dolog(LOG_DEBUG, 0, "group %s joined on vif %d",
1145 inet_fmt(mcastgrp, s1), vifi);
1147 for (g = kernel_table; g; g = g->gt_gnext) {
1148 if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1152 if (g->gt_mcastgrp == mcastgrp &&
1153 VIFM_ISSET(vifi, r->rt_children)) {
1155 VIFM_SET(vifi, g->gt_grpmems);
1157 if (VIFM_ISEMPTY(g->gt_grpmems))
1161 IF_DEBUG(DEBUG_CACHE)
1162 dolog(LOG_DEBUG, 0, "update lclgrp (%s %s) gm:%x",
1164 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1168 /* Send route change notification to reservation protocol. */
1169 rsrr_cache_send(g,1);
1176 * reset forwarding flag for all mcastgrps on this vifi
1179 delete_lclgrp(vifi_t vifi, u_int32 mcastgrp)
1183 IF_DEBUG(DEBUG_MEMBER)
1184 dolog(LOG_DEBUG, 0, "group %s left on vif %d",
1185 inet_fmt(mcastgrp, s1), vifi);
1187 for (g = kernel_table; g; g = g->gt_gnext) {
1188 if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1191 if (g->gt_mcastgrp == mcastgrp && VIFM_ISSET(vifi, g->gt_grpmems)) {
1192 if (g->gt_route == NULL ||
1193 SUBS_ARE_PRUNED(g->gt_route->rt_subordinates,
1194 uvifs[vifi].uv_nbrmap, g->gt_prunes)) {
1195 VIFM_CLR(vifi, g->gt_grpmems);
1196 IF_DEBUG(DEBUG_CACHE)
1197 dolog(LOG_DEBUG, 0, "delete lclgrp (%s %s) gm:%x",
1198 RT_FMT(g->gt_route, s1),
1199 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1204 /* Send route change notification to reservation protocol. */
1205 rsrr_cache_send(g,1);
1209 * If there are no more members of this particular group,
1210 * send prune upstream
1212 if (VIFM_ISEMPTY(g->gt_grpmems) && g->gt_route->rt_gateway)
1220 * Takes the prune message received and then strips it to
1221 * determine the (src, grp) pair to be pruned.
1223 * Adds the router to the (src, grp) entry then.
1225 * Determines if further packets have to be sent down that vif
1227 * Determines if a corresponding prune message has to be generated
1230 accept_prune(u_int32 src, u_int32 dst, char *p, int datalen)
1241 if ((vifi = find_vif(src, dst)) == NO_VIF) {
1243 "ignoring prune report from non-neighbor %s",
1248 /* Check if enough data is present */
1251 dolog(LOG_WARNING, 0,
1252 "non-decipherable prune from %s",
1257 for (i = 0; i< 4; i++)
1258 ((char *)&prun_src)[i] = *p++;
1259 for (i = 0; i< 4; i++)
1260 ((char *)&prun_grp)[i] = *p++;
1261 for (i = 0; i< 4; i++)
1262 ((char *)&prun_tmr)[i] = *p++;
1263 prun_tmr = ntohl(prun_tmr);
1265 if (prun_tmr <= MIN_PRUNE_LIFE) {
1266 IF_DEBUG(DEBUG_PRUNE)
1267 dolog(LOG_DEBUG, 0, "ignoring prune from %s on vif %d for (%s %s)/%d because its lifetime is too short",
1268 inet_fmt(src, s1), vifi,
1269 inet_fmt(prun_src, s2), inet_fmt(prun_grp, s3), prun_tmr);
1273 IF_DEBUG(DEBUG_PRUNE)
1274 dolog(LOG_DEBUG, 0, "%s on vif %d prunes (%s %s)/%d",
1275 inet_fmt(src, s1), vifi,
1276 inet_fmt(prun_src, s2), inet_fmt(prun_grp, s3), prun_tmr);
1279 * Find the subnet for the prune
1281 if (find_src_grp(prun_src, 0, prun_grp)) {
1282 g = gtp ? gtp->gt_gnext : kernel_table;
1285 IF_DEBUG(DEBUG_PRUNE)
1286 dolog(LOG_DEBUG, 0, "found grp state, (%s %s), metric is %d, children are %x, subords are %08x%08x",
1287 RT_FMT(r, s1), inet_fmt(g->gt_mcastgrp, s2), r->rt_metric,
1288 r->rt_children, r->rt_subordinates.hi, r->rt_subordinates.lo);
1289 if (!VIFM_ISSET(vifi, r->rt_children)) {
1290 IF_DEBUG(DEBUG_PRUNE)
1291 dolog(LOG_WARNING, 0, "prune received from non-child %s for (%s %s) (dominant on vif %d is %s)",
1292 inet_fmt(src, s1), inet_fmt(prun_src, s2),
1293 inet_fmt(prun_grp, s3), vifi,
1294 inet_fmt(r->rt_dominants[vifi], s4));
1300 if (VIFM_ISSET(vifi, g->gt_scope)) {
1301 dolog(LOG_WARNING, 0, "prune received from %s on scoped grp (%s %s)",
1302 inet_fmt(src, s1), inet_fmt(prun_src, s2),
1303 inet_fmt(prun_grp, s3));
1306 if ((pt = find_prune_entry(src, g->gt_pruntbl)) != NULL) {
1307 IF_DEBUG(DEBUG_PRUNE)
1308 dolog(LOG_DEBUG, 0, "%s %d from %s for (%s %s)/%d %s %d %s %x",
1309 "duplicate prune received on vif",
1310 vifi, inet_fmt(src, s1), inet_fmt(prun_src, s2),
1311 inet_fmt(prun_grp, s3), prun_tmr,
1312 "old timer:", pt->pt_timer, "cur gm:", g->gt_grpmems);
1313 pt->pt_timer = prun_tmr;
1315 struct listaddr *n = neighbor_info(vifi, src);
1318 dolog(LOG_WARNING, 0, "Prune from non-neighbor %s on vif %d!?",
1319 inet_fmt(src, s1), vifi);
1323 /* allocate space for the prune structure */
1324 pt = (struct ptable *)(malloc(sizeof(struct ptable)));
1326 dolog(LOG_ERR, 0, "pt: ran out of memory");
1329 pt->pt_router = src;
1330 pt->pt_timer = prun_tmr;
1332 pt->pt_next = g->gt_pruntbl;
1336 pt->pt_index = n->al_index;
1337 NBRM_SET(n->al_index, g->gt_prunes);
1342 * check if any more packets need to be sent on the
1343 * vif which sent this message
1345 if (SUBS_ARE_PRUNED(r->rt_subordinates,
1346 uvifs[vifi].uv_nbrmap, g->gt_prunes) &&
1347 !grplst_mem(vifi, prun_grp)) {
1350 VIFM_CLR(vifi, g->gt_grpmems);
1351 IF_DEBUG(DEBUG_PRUNE)
1352 dolog(LOG_DEBUG, 0, "vifnbrs=0x%08x%08x, subord=0x%08x%08x prunes=0x%08x%08x",
1353 uvifs[vifi].uv_nbrmap.hi,uvifs[vifi].uv_nbrmap.lo,
1354 r->rt_subordinates.hi, r->rt_subordinates.lo,
1355 g->gt_prunes.hi, g->gt_prunes.lo);
1357 NBRM_COPY(r->rt_subordinates, tmp);
1358 NBRM_MASK(tmp, uvifs[vifi].uv_nbrmap);
1359 if (!NBRM_ISSETALLMASK(g->gt_prunes, tmp))
1360 dolog(LOG_WARNING, 0, "subordinate error");
1361 /* XXX end debugging */
1362 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1363 dolog(LOG_DEBUG, 0, "prune (%s %s), stop sending on vif %d, gm:%x",
1365 inet_fmt(g->gt_mcastgrp, s2), vifi, g->gt_grpmems);
1370 /* Send route change notification to reservation protocol. */
1371 rsrr_cache_send(g,1);
1376 * check if all the child routers have expressed no interest
1377 * in this group and if this group does not exist in the
1379 * Send a prune message then upstream
1381 if (VIFM_ISEMPTY(g->gt_grpmems) && r->rt_gateway) {
1386 * There is no kernel entry for this group. Therefore, we can
1387 * simply ignore the prune, as we are not forwarding this traffic
1390 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1391 dolog(LOG_DEBUG, 0, "%s (%s %s)/%d from %s",
1392 "prune message received with no kernel entry for",
1393 inet_fmt(prun_src, s1), inet_fmt(prun_grp, s2),
1394 prun_tmr, inet_fmt(src, s3));
1400 * Checks if this mcastgrp is present in the kernel table
1401 * If so and if a prune was sent, it sends a graft upwards
1404 chkgrp_graft(vifi_t vifi, u_int32 mcastgrp)
1409 for (g = kernel_table; g; g = g->gt_gnext) {
1410 if (ntohl(mcastgrp) < ntohl(g->gt_mcastgrp))
1414 if (g->gt_mcastgrp == mcastgrp && VIFM_ISSET(vifi, r->rt_children))
1415 if (g->gt_prsent_timer) {
1416 VIFM_SET(vifi, g->gt_grpmems);
1419 * If the vif that was joined was a scoped vif,
1420 * ignore it ; don't graft back
1423 if (VIFM_ISEMPTY(g->gt_grpmems))
1426 /* send graft upwards */
1429 /* update cache timer*/
1430 g->gt_timer = CACHE_LIFETIME(cache_lifetime);
1432 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1433 dolog(LOG_DEBUG, 0, "chkgrp graft (%s %s) gm:%x",
1435 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1440 /* Send route change notification to reservation protocol. */
1441 rsrr_cache_send(g,1);
1447 /* determine the multicast group and src
1449 * if it does, then determine if a prune was sent
1451 * if prune sent upstream, send graft upstream and send
1454 * if no prune sent upstream, change the forwarding bit
1455 * for this interface and send ack downstream.
1457 * if no entry exists for this group send ack downstream.
1460 accept_graft(u_int32 src, u_int32 dst, char *p, int datalen)
1468 struct ptable *pt, **ptnp;
1471 dolog(LOG_WARNING, 0,
1472 "received non-decipherable graft from %s",
1477 for (i = 0; i< 4; i++)
1478 ((char *)&graft_src)[i] = *p++;
1479 for (i = 0; i< 4; i++)
1480 ((char *)&graft_grp)[i] = *p++;
1482 vifi = find_vif(src, dst);
1483 send_graft_ack(dst, src, graft_src, graft_grp, vifi);
1485 if (vifi == NO_VIF) {
1487 "ignoring graft for (%s %s) from non-neighbor %s",
1488 inet_fmt(graft_src, s2), inet_fmt(graft_grp, s3),
1493 IF_DEBUG(DEBUG_PRUNE)
1494 dolog(LOG_DEBUG, 0, "%s on vif %d grafts (%s %s)",
1495 inet_fmt(src, s1), vifi,
1496 inet_fmt(graft_src, s2), inet_fmt(graft_grp, s3));
1499 * Find the subnet for the graft
1501 if (find_src_grp(graft_src, 0, graft_grp)) {
1502 g = gtp ? gtp->gt_gnext : kernel_table;
1505 if (VIFM_ISSET(vifi, g->gt_scope)) {
1506 dolog(LOG_WARNING, 0, "graft received from %s on scoped grp (%s %s)",
1507 inet_fmt(src, s1), inet_fmt(graft_src, s2),
1508 inet_fmt(graft_grp, s3));
1512 ptnp = &g->gt_pruntbl;
1513 while ((pt = *ptnp) != NULL) {
1514 if ((pt->pt_vifi == vifi) && (pt->pt_router == src)) {
1515 NBRM_CLR(pt->pt_index, g->gt_prunes);
1516 *ptnp = pt->pt_next;
1519 VIFM_SET(vifi, g->gt_grpmems);
1520 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1521 dolog(LOG_DEBUG, 0, "accept graft (%s %s) gm:%x",
1523 inet_fmt(g->gt_mcastgrp, s2), g->gt_grpmems);
1528 /* Send route change notification to reservation protocol. */
1529 rsrr_cache_send(g,1);
1533 ptnp = &pt->pt_next;
1537 g->gt_timer = CACHE_LIFETIME(cache_lifetime);
1539 if (g->gt_prsent_timer)
1540 /* send graft upwards */
1544 * We have no state for the source and group in question.
1545 * This is fine, since we know that we have no prune state, and
1546 * grafts are requests to remove prune state.
1548 IF_DEBUG(DEBUG_PRUNE)
1549 dolog(LOG_DEBUG, 0, "%s (%s %s) from %s",
1550 "graft received with no kernel entry for",
1551 inet_fmt(graft_src, s1), inet_fmt(graft_grp, s2),
1558 * find out which group is involved first of all
1559 * then determine if a graft was sent.
1560 * if no graft sent, ignore the message
1561 * if graft was sent and the ack is from the right
1562 * source, remove the graft timer so that we don't
1563 * have send a graft again
1566 accept_g_ack(u_int32 src, u_int32 dst, char *p, int datalen)
1574 if ((vifi = find_vif(src, dst)) == NO_VIF) {
1576 "ignoring graft ack from non-neighbor %s",
1581 if (datalen < 0 || datalen > 8) {
1582 dolog(LOG_WARNING, 0,
1583 "received non-decipherable graft ack from %s",
1588 for (i = 0; i< 4; i++)
1589 ((char *)&grft_src)[i] = *p++;
1590 for (i = 0; i< 4; i++)
1591 ((char *)&grft_grp)[i] = *p++;
1593 IF_DEBUG(DEBUG_PRUNE)
1594 dolog(LOG_DEBUG, 0, "%s on vif %d acks graft (%s, %s)",
1595 inet_fmt(src, s1), vifi,
1596 inet_fmt(grft_src, s2), inet_fmt(grft_grp, s3));
1599 * Find the subnet for the graft ack
1601 if (find_src_grp(grft_src, 0, grft_grp)) {
1602 g = gtp ? gtp->gt_gnext : kernel_table;
1605 dolog(LOG_WARNING, 0, "%s (%s, %s) from %s",
1606 "rcvd graft ack with no kernel entry for",
1607 inet_fmt(grft_src, s1), inet_fmt(grft_grp, s2),
1618 * free all prune entries and kernel routes
1619 * normally, this should inform the kernel that all of its routes
1620 * are going away, but this is only called by restart(), which is
1621 * about to call MRT_DONE which does that anyway.
1624 free_all_prunes(void)
1627 struct gtable *g, *prev_g;
1628 struct stable *s, *prev_s;
1629 struct ptable *p, *prev_p;
1631 for (r = routing_table; r; r = r->rt_next) {
1650 if (prev_g->gt_rexmit_timer)
1651 timer_clearTimer(prev_g->gt_rexmit_timer);
1654 r->rt_groups = NULL;
1656 kernel_table = NULL;
1658 g = kernel_no_route;
1665 if (prev_g->gt_rexmit_timer)
1666 timer_clearTimer(prev_g->gt_rexmit_timer);
1669 kernel_no_route = NULL;
1673 * When a new route is created, search
1674 * a) The less-specific part of the routing table
1675 * b) The route-less kernel table
1676 * for sources that the new route might want to handle.
1678 * "Inheriting" these sources might be cleanest, but simply deleting
1679 * them is easier, and letting the kernel re-request them.
1682 steal_sources(struct rtentry *rt)
1685 struct gtable *gt, **gtnp;
1686 struct stable *st, **stnp;
1688 for (rp = rt->rt_next; rp; rp = rp->rt_next) {
1689 if (rp->rt_groups == NULL)
1691 if ((rt->rt_origin & rp->rt_originmask) == rp->rt_origin) {
1692 IF_DEBUG(DEBUG_ROUTE)
1693 dolog(LOG_DEBUG, 0, "Route for %s stealing sources from %s",
1694 RT_FMT(rt, s1), RT_FMT(rp, s2));
1695 for (gt = rp->rt_groups; gt; gt = gt->gt_next) {
1696 stnp = >->gt_srctbl;
1697 while ((st = *stnp) != NULL) {
1698 if ((st->st_origin & rt->rt_originmask) == rt->rt_origin) {
1699 IF_DEBUG(DEBUG_ROUTE)
1700 dolog(LOG_DEBUG, 0, "%s stealing (%s %s) from %s",
1702 inet_fmt(st->st_origin, s3),
1703 inet_fmt(gt->gt_mcastgrp, s4),
1705 if (st->st_ctime != 0) {
1706 if (k_del_rg(st->st_origin, gt) < 0) {
1707 dolog(LOG_WARNING, errno, "%s (%s, %s)",
1708 "steal_sources trying to delete",
1709 inet_fmt(st->st_origin, s1),
1710 inet_fmt(gt->gt_mcastgrp, s2));
1714 *stnp = st->st_next;
1717 stnp = &st->st_next;
1724 gtnp = &kernel_no_route;
1725 while ((gt = *gtnp) != NULL) {
1726 if (gt->gt_srctbl && ((gt->gt_srctbl->st_origin & rt->rt_originmask)
1727 == rt->rt_origin)) {
1728 IF_DEBUG(DEBUG_ROUTE)
1729 dolog(LOG_DEBUG, 0, "%s stealing (%s %s) from %s",
1731 inet_fmt(gt->gt_srctbl->st_origin, s3),
1732 inet_fmt(gt->gt_mcastgrp, s4),
1734 if (gt->gt_srctbl->st_ctime != 0) {
1735 if (k_del_rg(gt->gt_srctbl->st_origin, gt) < 0) {
1736 dolog(LOG_WARNING, errno, "%s (%s %s)",
1737 "steal_sources trying to delete",
1738 inet_fmt(gt->gt_srctbl->st_origin, s1),
1739 inet_fmt(gt->gt_mcastgrp, s2));
1743 free(gt->gt_srctbl);
1744 *gtnp = gt->gt_next;
1746 gt->gt_next->gt_prev = gt->gt_prev;
1747 if (gt->gt_rexmit_timer)
1748 timer_clearTimer(gt->gt_rexmit_timer);
1751 gtnp = >->gt_next;
1757 * Advance the timers on all the cache entries.
1758 * If there are any entries whose timers have expired,
1759 * remove these entries from the kernel cache.
1762 age_table_entry(void)
1765 struct gtable *gt, **gtnptr;
1766 struct stable *st, **stnp;
1767 struct ptable *pt, **ptnp;
1768 struct sioc_sg_req sg_req;
1770 IF_DEBUG(DEBUG_PRUNE|DEBUG_CACHE)
1771 dolog(LOG_DEBUG, 0, "aging forwarding cache entries");
1773 gtnptr = &kernel_table;
1774 while ((gt = *gtnptr) != NULL) {
1775 vifi_t i; /* XXX Debugging */
1776 int fixit = 0; /* XXX Debugging */
1780 /* XXX Debugging... */
1781 for (i = 0; i < numvifs; i++) {
1783 * If we're not sending on this vif,
1784 * And this group isn't scoped on this vif,
1785 * And I'm the parent for this route on this vif,
1786 * And there are subordinates on this vif,
1787 * And all of the subordinates haven't pruned,
1789 * and remember to fix it up later
1791 if (!VIFM_ISSET(i, gt->gt_grpmems) &&
1792 !VIFM_ISSET(i, gt->gt_scope) &&
1793 VIFM_ISSET(i, r->rt_children) &&
1794 NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates) &&
1795 !SUBS_ARE_PRUNED(r->rt_subordinates, uvifs[i].uv_nbrmap, gt->gt_prunes)) {
1796 dolog(LOG_WARNING, 0, "(%s %s) is blackholing on vif %d",
1797 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), i);
1802 dolog(LOG_WARNING, 0, "fixing membership for (%s %s) gm:%x",
1803 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems);
1804 determine_forwvifs(gt);
1805 send_prune_or_graft(gt);
1806 dolog(LOG_WARNING, 0, "fixed membership for (%s %s) gm:%x",
1807 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems);
1813 /* If there are group members,
1814 * and there are recent sources,
1815 * and we have a route,
1816 * and it's not directly connected,
1817 * and we haven't sent a prune,
1818 * if there are any cache entries in the kernel
1819 * [if there aren't we're probably waiting to rexmit],
1823 if (VIFM_ISEMPTY(gt->gt_grpmems) && gt->gt_srctbl && r && r->rt_gateway && gt->gt_prsent_timer == 0) {
1824 for (st = gt->gt_srctbl; st; st = st->st_next)
1825 if (st->st_ctime != 0)
1828 dolog(LOG_WARNING, 0, "grpmems for (%s %s) is empty but no prune state!", RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
1829 send_prune_or_graft(gt);
1835 /* XXX ...Debugging */
1837 /* advance the timer for the kernel entry */
1838 gt->gt_timer -= TIMER_INTERVAL;
1840 /* decrement prune timer if need be */
1841 if (gt->gt_prsent_timer > 0) {
1842 gt->gt_prsent_timer -= TIMER_INTERVAL;
1843 if (gt->gt_prsent_timer <= 0) {
1844 IF_DEBUG(DEBUG_PRUNE)
1845 dolog(LOG_DEBUG, 0, "upstream prune tmo (%s %s)",
1847 inet_fmt(gt->gt_mcastgrp, s2));
1848 gt->gt_prsent_timer = -1;
1849 /* Reset the prune retransmission timer to its initial value */
1850 gt->gt_prune_rexmit = PRUNE_REXMIT_VAL;
1854 /* retransmit graft with exponential backoff */
1855 if (gt->gt_grftsnt) {
1858 y = ++gt->gt_grftsnt;
1859 while (y && !(y & 1))
1868 * If a prune expires, forward again on that vif.
1870 ptnp = >->gt_pruntbl;
1871 while ((pt = *ptnp) != NULL) {
1872 if ((pt->pt_timer -= TIMER_INTERVAL) <= 0) {
1873 IF_DEBUG(DEBUG_PRUNE)
1874 dolog(LOG_DEBUG, 0, "expire prune (%s %s) from %s on vif %d",
1876 inet_fmt(gt->gt_mcastgrp, s2),
1877 inet_fmt(pt->pt_router, s3),
1879 if (gt->gt_prsent_timer > 0) {
1880 dolog(LOG_WARNING, 0, "prune (%s %s) from %s on vif %d expires with %d left on prsent timer",
1882 inet_fmt(gt->gt_mcastgrp, s2),
1883 inet_fmt(pt->pt_router, s3),
1884 pt->pt_vifi, gt->gt_prsent_timer);
1885 /* Send a graft to heal the tree. */
1889 NBRM_CLR(pt->pt_index, gt->gt_prunes);
1890 expire_prune(pt->pt_vifi, gt);
1892 /* remove the router's prune entry and await new one */
1893 *ptnp = pt->pt_next;
1896 ptnp = &pt->pt_next;
1901 * If the cache entry has expired, delete source table entries for
1902 * silent sources. If there are no source entries left, and there
1903 * are no downstream prunes, then the entry is deleted.
1904 * Otherwise, the cache entry's timer is refreshed.
1906 if (gt->gt_timer <= 0) {
1907 IF_DEBUG(DEBUG_CACHE)
1908 dolog(LOG_DEBUG, 0, "(%s %s) timed out, checking for traffic",
1909 RT_FMT(gt->gt_route, s1),
1910 inet_fmt(gt->gt_mcastgrp, s2));
1911 /* Check for traffic before deleting source entries */
1912 sg_req.grp.s_addr = gt->gt_mcastgrp;
1913 stnp = >->gt_srctbl;
1914 while ((st = *stnp) != NULL) {
1916 * Source entries with no ctime are not actually in the
1917 * kernel; they have been removed by rexmit_prune() so
1918 * are safe to remove from the list at this point.
1921 sg_req.src.s_addr = st->st_origin;
1922 if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
1923 dolog(LOG_WARNING, errno, "%s (%s %s)",
1924 "age_table_entry: SIOCGETSGCNT failing for",
1925 inet_fmt(st->st_origin, s1),
1926 inet_fmt(gt->gt_mcastgrp, s2));
1927 /* Make sure it gets deleted below */
1928 sg_req.pktcnt = st->st_pktcnt;
1931 sg_req.pktcnt = st->st_pktcnt;
1933 if (sg_req.pktcnt == st->st_pktcnt) {
1934 *stnp = st->st_next;
1935 IF_DEBUG(DEBUG_CACHE)
1936 dolog(LOG_DEBUG, 0, "age_table_entry deleting (%s %s)",
1937 inet_fmt(st->st_origin, s1),
1938 inet_fmt(gt->gt_mcastgrp, s2));
1939 if (st->st_ctime != 0) {
1940 if (k_del_rg(st->st_origin, gt) < 0) {
1941 dolog(LOG_WARNING, errno,
1942 "age_table_entry trying to delete (%s %s)",
1943 inet_fmt(st->st_origin, s1),
1944 inet_fmt(gt->gt_mcastgrp, s2));
1950 st->st_pktcnt = sg_req.pktcnt;
1951 stnp = &st->st_next;
1956 * Retain the group entry if we have downstream prunes or if
1957 * there is at least one source in the list that still has
1958 * traffic, or if our upstream prune timer or graft
1959 * retransmission timer is running.
1961 if (gt->gt_pruntbl != NULL || gt->gt_srctbl != NULL ||
1962 gt->gt_prsent_timer > 0 || gt->gt_grftsnt > 0) {
1963 IF_DEBUG(DEBUG_CACHE)
1964 dolog(LOG_DEBUG, 0, "refresh lifetim of cache entry %s%s%s%s(%s, %s)",
1965 gt->gt_pruntbl ? "(dstrm prunes) " : "",
1966 gt->gt_srctbl ? "(trfc flow) " : "",
1967 gt->gt_prsent_timer > 0 ? "(upstrm prune) " : "",
1968 gt->gt_grftsnt > 0 ? "(grft rexmit) " : "",
1970 inet_fmt(gt->gt_mcastgrp, s2));
1971 gt->gt_timer = CACHE_LIFETIME(cache_lifetime);
1972 if (gt->gt_prsent_timer == -1) {
1974 * The upstream prune timed out. Remove any kernel
1977 gt->gt_prsent_timer = 0;
1978 if (gt->gt_pruntbl) {
1979 dolog(LOG_WARNING, 0, "upstream prune for (%s %s) expires with downstream prunes active",
1980 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
1984 gtnptr = >->gt_gnext;
1988 IF_DEBUG(DEBUG_CACHE)
1989 dolog(LOG_DEBUG, 0, "timeout cache entry (%s, %s)",
1991 inet_fmt(gt->gt_mcastgrp, s2));
1994 gt->gt_prev->gt_next = gt->gt_next;
1996 gt->gt_route->rt_groups = gt->gt_next;
1998 gt->gt_next->gt_prev = gt->gt_prev;
2001 gt->gt_gprev->gt_gnext = gt->gt_gnext;
2002 gtnptr = >->gt_gprev->gt_gnext;
2004 kernel_table = gt->gt_gnext;
2005 gtnptr = &kernel_table;
2008 gt->gt_gnext->gt_gprev = gt->gt_gprev;
2011 /* Send route change notification to reservation protocol. */
2012 rsrr_cache_send(gt,0);
2013 rsrr_cache_clean(gt);
2015 if (gt->gt_rexmit_timer)
2016 timer_clearTimer(gt->gt_rexmit_timer);
2020 if (gt->gt_prsent_timer == -1) {
2022 * The upstream prune timed out. Remove any kernel
2025 gt->gt_prsent_timer = 0;
2026 if (gt->gt_pruntbl) {
2027 dolog(LOG_WARNING, 0, "upstream prune for (%s %s) expires with downstream prunes active",
2028 RT_FMT(r, s1), inet_fmt(gt->gt_mcastgrp, s2));
2032 gtnptr = >->gt_gnext;
2037 * When traversing the no_route table, the decision is much easier.
2038 * Just delete it if it has timed out.
2040 gtnptr = &kernel_no_route;
2041 while ((gt = *gtnptr) != NULL) {
2042 /* advance the timer for the kernel entry */
2043 gt->gt_timer -= TIMER_INTERVAL;
2045 if (gt->gt_timer < 0) {
2046 if (gt->gt_srctbl) {
2047 if (gt->gt_srctbl->st_ctime != 0) {
2048 if (k_del_rg(gt->gt_srctbl->st_origin, gt) < 0) {
2049 dolog(LOG_WARNING, errno, "%s (%s %s)",
2050 "age_table_entry trying to delete no-route",
2051 inet_fmt(gt->gt_srctbl->st_origin, s1),
2052 inet_fmt(gt->gt_mcastgrp, s2));
2056 free(gt->gt_srctbl);
2058 *gtnptr = gt->gt_next;
2060 gt->gt_next->gt_prev = gt->gt_prev;
2062 if (gt->gt_rexmit_timer)
2063 timer_clearTimer(gt->gt_rexmit_timer);
2067 gtnptr = >->gt_next;
2073 * Modify the kernel to forward packets when one or multiple prunes that
2074 * were received on the vif given by vifi, for the group given by gt,
2078 expire_prune(vifi_t vifi, struct gtable *gt)
2081 * No need to send a graft, any prunes that we sent
2082 * will expire before any prunes that we have received.
2083 * However, in the case that we did make a mistake,
2084 * send a graft to compensate.
2086 if (gt->gt_prsent_timer >= MIN_PRUNE_LIFE) {
2087 IF_DEBUG(DEBUG_PRUNE)
2088 dolog(LOG_DEBUG, 0, "prune expired with %d left on %s",
2089 gt->gt_prsent_timer, "prsent_timer");
2090 gt->gt_prsent_timer = 0;
2094 /* modify the kernel entry to forward packets */
2095 if (!VIFM_ISSET(vifi, gt->gt_grpmems)) {
2096 struct rtentry *rt = gt->gt_route;
2097 VIFM_SET(vifi, gt->gt_grpmems);
2098 IF_DEBUG(DEBUG_CACHE)
2099 dolog(LOG_DEBUG, 0, "forw again (%s %s) gm:%x vif:%d",
2101 inet_fmt(gt->gt_mcastgrp, s2), gt->gt_grpmems, vifi);
2106 /* Send route change notification to reservation protocol. */
2107 rsrr_cache_send(gt,1);
2113 * Print the contents of the cache table on file 'fp2'.
2116 dump_cache(FILE *fp2)
2128 "Multicast Routing Cache Table (%d entries)\n%s", kroutes,
2129 " Origin Mcast-group CTmr Age Ptmr Rx IVif Forwvifs\n");
2131 "<(prunesrc:vif[idx]/tmr) prunebitmap\n%s",
2132 ">Source Lifetime SavPkt Pkts Bytes RPFf\n");
2134 for (gt = kernel_no_route; gt; gt = gt->gt_next) {
2135 if (gt->gt_srctbl) {
2136 fprintf(fp2, " %-18s %-15s %-8s %-8s - -1 (no route)\n",
2137 inet_fmts(gt->gt_srctbl->st_origin, 0xffffffff, s1),
2138 inet_fmt(gt->gt_mcastgrp, s2), scaletime(gt->gt_timer),
2139 scaletime(thyme - gt->gt_ctime));
2140 fprintf(fp2, ">%s\n", inet_fmt(gt->gt_srctbl->st_origin, s1));
2144 for (gt = kernel_table; gt; gt = gt->gt_gnext) {
2146 fprintf(fp2, " %-18s %-15s",
2148 inet_fmt(gt->gt_mcastgrp, s2));
2150 fprintf(fp2, " %-8s", scaletime(gt->gt_timer));
2152 fprintf(fp2, " %-8s %-8s ", scaletime(thyme - gt->gt_ctime),
2153 gt->gt_prsent_timer ? scaletime(gt->gt_prsent_timer) :
2156 if (gt->gt_prune_rexmit) {
2157 int i = gt->gt_prune_rexmit;
2160 while (i > PRUNE_REXMIT_VAL) {
2164 if (n == 0 && gt->gt_prsent_timer == 0)
2167 fprintf(fp2, "%2d", n);
2172 fprintf(fp2, " %2u%c%c", r->rt_parent,
2173 gt->gt_prsent_timer ? 'P' :
2174 gt->gt_grftsnt ? 'G' : ' ',
2175 VIFM_ISSET(r->rt_parent, gt->gt_scope) ? 'B' : ' ');
2177 for (i = 0; i < numvifs; ++i) {
2178 if (VIFM_ISSET(i, gt->gt_grpmems))
2179 fprintf(fp2, " %u ", i);
2180 else if (VIFM_ISSET(i, r->rt_children) &&
2181 NBRM_ISSETMASK(uvifs[i].uv_nbrmap, r->rt_subordinates))
2182 fprintf(fp2, " %u%c", i,
2183 VIFM_ISSET(i, gt->gt_scope) ? 'b' :
2184 SUBS_ARE_PRUNED(r->rt_subordinates,
2185 uvifs[i].uv_nbrmap, gt->gt_prunes) ? 'p' : '!');
2188 if (gt->gt_pruntbl) {
2191 for (pt = gt->gt_pruntbl; pt; pt = pt->pt_next) {
2192 fprintf(fp2, "%c%s:%d[%d]/%d", c, inet_fmt(pt->pt_router, s1),
2193 pt->pt_vifi, pt->pt_index, pt->pt_timer);
2197 fprintf(fp2, " 0x%08lx%08lx\n",/*XXX*/
2198 gt->gt_prunes.hi, gt->gt_prunes.lo);
2200 for (st = gt->gt_srctbl; st; st = st->st_next) {
2201 fprintf(fp2, ">%-18s %-8s %6ld", inet_fmt(st->st_origin, s1),
2202 st->st_ctime ? scaletime(thyme - st->st_ctime) : "-",
2205 struct sioc_sg_req sg_req;
2207 sg_req.src.s_addr = st->st_origin;
2208 sg_req.grp.s_addr = gt->gt_mcastgrp;
2209 if (ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) < 0) {
2210 dolog(LOG_WARNING, errno, "SIOCGETSGCNT on (%s %s)",
2211 inet_fmt(st->st_origin, s1),
2212 inet_fmt(gt->gt_mcastgrp, s2));
2214 fprintf(fp2, " %8ld %8ld %4ld", sg_req.pktcnt,
2215 sg_req.bytecnt, sg_req.wrong_if);
2224 * Traceroute function which returns traceroute replies to the requesting
2225 * router. Also forwards the request to downstream routers.
2228 accept_mtrace(u_int32 src, u_int32 dst, u_int32 group, char *data,
2229 u_int no, /* promoted u_char */
2235 struct tr_query *qry;
2236 struct tr_resp *resp;
2240 int errcode = TR_NO_ERR;
2243 struct sioc_vif_req v_req;
2244 struct sioc_sg_req sg_req;
2246 /* Remember qid across invocations */
2247 static u_int32 oqid = 0;
2249 /* timestamp the request/response */
2250 gettimeofday(&tp, 0);
2253 * Check if it is a query or a response
2255 if (datalen == QLEN) {
2257 IF_DEBUG(DEBUG_TRACE)
2258 dolog(LOG_DEBUG, 0, "Initial traceroute query rcvd from %s to %s",
2259 inet_fmt(src, s1), inet_fmt(dst, s2));
2261 else if ((datalen - QLEN) % RLEN == 0) {
2263 IF_DEBUG(DEBUG_TRACE)
2264 dolog(LOG_DEBUG, 0, "In-transit traceroute query rcvd from %s to %s",
2265 inet_fmt(src, s1), inet_fmt(dst, s2));
2266 if (IN_MULTICAST(ntohl(dst))) {
2267 IF_DEBUG(DEBUG_TRACE)
2268 dolog(LOG_DEBUG, 0, "Dropping multicast response");
2273 dolog(LOG_WARNING, 0, "%s from %s to %s",
2274 "Non decipherable traceroute request received",
2275 inet_fmt(src, s1), inet_fmt(dst, s2));
2279 qry = (struct tr_query *)data;
2282 * if it is a packet with all reports filled, drop it
2284 if ((rcount = (datalen - QLEN)/RLEN) == no) {
2285 IF_DEBUG(DEBUG_TRACE)
2286 dolog(LOG_DEBUG, 0, "packet with all reports filled in");
2290 IF_DEBUG(DEBUG_TRACE) {
2291 dolog(LOG_DEBUG, 0, "s: %s g: %s d: %s ", inet_fmt(qry->tr_src, s1),
2292 inet_fmt(group, s2), inet_fmt(qry->tr_dst, s3));
2293 dolog(LOG_DEBUG, 0, "rttl: %d rd: %s", qry->tr_rttl,
2294 inet_fmt(qry->tr_raddr, s1));
2295 dolog(LOG_DEBUG, 0, "rcount:%d, qid:%06x", rcount, qry->tr_qid);
2298 /* determine the routing table entry for this traceroute */
2299 rt = determine_route(qry->tr_src);
2300 IF_DEBUG(DEBUG_TRACE)
2302 dolog(LOG_DEBUG, 0, "rt parent vif: %d rtr: %s metric: %d",
2303 rt->rt_parent, inet_fmt(rt->rt_gateway, s1), rt->rt_metric);
2304 dolog(LOG_DEBUG, 0, "rt origin %s",
2307 dolog(LOG_DEBUG, 0, "...no route");
2310 * Query type packet - check if rte exists
2311 * Check if the query destination is a vif connected to me.
2312 * and if so, whether I should start response back
2314 if (type == QUERY) {
2315 if (oqid == qry->tr_qid) {
2317 * If the multicast router is a member of the group being
2318 * queried, and the query is multicasted, then the router can
2319 * recieve multiple copies of the same query. If we have already
2320 * replied to this traceroute, just ignore it this time.
2322 * This is not a total solution, but since if this fails you
2323 * only get N copies, N <= the number of interfaces on the router,
2326 IF_DEBUG(DEBUG_TRACE)
2327 dolog(LOG_DEBUG, 0, "ignoring duplicate traceroute packet");
2332 IF_DEBUG(DEBUG_TRACE)
2333 dolog(LOG_DEBUG, 0, "Mcast traceroute: no route entry %s",
2334 inet_fmt(qry->tr_src, s1));
2335 if (IN_MULTICAST(ntohl(dst)))
2338 vifi = find_vif(qry->tr_dst, 0);
2340 if (vifi == NO_VIF) {
2341 /* The traceroute destination is not on one of my subnet vifs. */
2342 IF_DEBUG(DEBUG_TRACE)
2343 dolog(LOG_DEBUG, 0, "Destination %s not an interface",
2344 inet_fmt(qry->tr_dst, s1));
2345 if (IN_MULTICAST(ntohl(dst)))
2347 errcode = TR_WRONG_IF;
2348 } else if (rt != NULL && !VIFM_ISSET(vifi, rt->rt_children)) {
2349 IF_DEBUG(DEBUG_TRACE)
2350 dolog(LOG_DEBUG, 0, "Destination %s not on forwarding tree for src %s",
2351 inet_fmt(qry->tr_dst, s1), inet_fmt(qry->tr_src, s2));
2352 if (IN_MULTICAST(ntohl(dst)))
2354 errcode = TR_WRONG_IF;
2359 * determine which interface the packet came in on
2360 * RESP packets travel hop-by-hop so this either traversed
2361 * a tunnel or came from a directly attached mrouter.
2363 if ((vifi = find_vif(src, dst)) == NO_VIF) {
2364 IF_DEBUG(DEBUG_TRACE)
2365 dolog(LOG_DEBUG, 0, "Wrong interface for packet");
2366 errcode = TR_WRONG_IF;
2370 /* Now that we've decided to send a response, save the qid */
2373 IF_DEBUG(DEBUG_TRACE)
2374 dolog(LOG_DEBUG, 0, "Sending traceroute response");
2376 /* copy the packet to the sending buffer */
2377 p = send_buf + MIN_IP_HEADER_LEN + IGMP_MINLEN;
2379 bcopy(data, p, datalen);
2384 * If there is no room to insert our reply, coopt the previous hop
2385 * error indication to relay this fact.
2387 if (p + sizeof(struct tr_resp) > send_buf + RECV_BUF_SIZE) {
2388 resp = (struct tr_resp *)p - 1;
2389 resp->tr_rflags = TR_NO_SPACE;
2395 * fill in initial response fields
2397 resp = (struct tr_resp *)p;
2398 bzero(resp, sizeof(struct tr_resp));
2401 resp->tr_qarr = htonl(((tp.tv_sec + JAN_1970) << 16) +
2402 ((tp.tv_usec << 10) / 15625));
2404 resp->tr_rproto = PROTO_DVMRP;
2405 resp->tr_outaddr = (vifi == NO_VIF) ? dst : uvifs[vifi].uv_lcl_addr;
2406 resp->tr_fttl = (vifi == NO_VIF) ? 0 : uvifs[vifi].uv_threshold;
2407 resp->tr_rflags = errcode;
2410 * obtain # of packets out on interface
2413 if (vifi != NO_VIF && ioctl(udp_socket, SIOCGETVIFCNT, (char *)&v_req) >= 0)
2414 resp->tr_vifout = htonl(v_req.ocount);
2416 resp->tr_vifout = 0xffffffff;
2419 * fill in scoping & pruning information
2422 for (gt = rt->rt_groups; gt; gt = gt->gt_next) {
2423 if (gt->gt_mcastgrp >= group)
2429 if (gt && gt->gt_mcastgrp == group) {
2432 for (st = gt->gt_srctbl; st; st = st->st_next)
2433 if (qry->tr_src == st->st_origin)
2436 sg_req.src.s_addr = qry->tr_src;
2437 sg_req.grp.s_addr = group;
2438 if (st && st->st_ctime != 0 &&
2439 ioctl(udp_socket, SIOCGETSGCNT, (char *)&sg_req) >= 0)
2440 resp->tr_pktcnt = htonl(sg_req.pktcnt + st->st_savpkt);
2442 resp->tr_pktcnt = htonl(st ? st->st_savpkt : 0xffffffff);
2444 if (VIFM_ISSET(vifi, gt->gt_scope))
2445 resp->tr_rflags = TR_SCOPED;
2446 else if (gt->gt_prsent_timer)
2447 resp->tr_rflags = TR_PRUNED;
2448 else if (!VIFM_ISSET(vifi, gt->gt_grpmems))
2449 if (!NBRM_ISEMPTY(uvifs[vifi].uv_nbrmap) &&
2450 SUBS_ARE_PRUNED(rt->rt_subordinates,
2451 uvifs[vifi].uv_nbrmap, gt->gt_prunes))
2452 resp->tr_rflags = TR_OPRUNED;
2454 resp->tr_rflags = TR_NO_FWD;
2456 if ((vifi != NO_VIF && scoped_addr(vifi, group)) ||
2457 (rt && scoped_addr(rt->rt_parent, group)))
2458 resp->tr_rflags = TR_SCOPED;
2459 else if (rt && !VIFM_ISSET(vifi, rt->rt_children))
2460 resp->tr_rflags = TR_NO_FWD;
2464 * if no rte exists, set NO_RTE error
2467 src = dst; /* the dst address of resp. pkt */
2468 resp->tr_inaddr = 0;
2469 resp->tr_rflags = TR_NO_RTE;
2470 resp->tr_rmtaddr = 0;
2472 /* get # of packets in on interface */
2473 v_req.vifi = rt->rt_parent;
2474 if (ioctl(udp_socket, SIOCGETVIFCNT, (char *)&v_req) >= 0)
2475 resp->tr_vifin = htonl(v_req.icount);
2477 resp->tr_vifin = 0xffffffff;
2479 MASK_TO_VAL(rt->rt_originmask, resp->tr_smask);
2480 src = uvifs[rt->rt_parent].uv_lcl_addr;
2481 resp->tr_inaddr = src;
2482 resp->tr_rmtaddr = rt->rt_gateway;
2483 if (!VIFM_ISSET(vifi, rt->rt_children)) {
2484 IF_DEBUG(DEBUG_TRACE)
2485 dolog(LOG_DEBUG, 0, "Destination %s not on forwarding tree for src %s",
2486 inet_fmt(qry->tr_dst, s1), inet_fmt(qry->tr_src, s2));
2487 resp->tr_rflags = TR_WRONG_IF;
2489 if (rt->rt_metric >= UNREACHABLE) {
2490 resp->tr_rflags = TR_NO_RTE;
2491 /* Hack to send reply directly */
2498 * if metric is 1 or no. of reports is 1, send response to requestor
2499 * else send to upstream router. If the upstream router can't handle
2500 * mtrace, set an error code and send to requestor anyway.
2502 IF_DEBUG(DEBUG_TRACE)
2503 dolog(LOG_DEBUG, 0, "rcount:%d, no:%d", rcount, no);
2505 if ((rcount + 1 == no) || (rt == NULL) || (rt->rt_metric == 1)) {
2506 resptype = IGMP_MTRACE_RESP;
2507 dst = qry->tr_raddr;
2509 if (!can_mtrace(rt->rt_parent, rt->rt_gateway)) {
2510 dst = qry->tr_raddr;
2511 resp->tr_rflags = TR_OLD_ROUTER;
2512 resptype = IGMP_MTRACE_RESP;
2514 dst = rt->rt_gateway;
2515 resptype = IGMP_MTRACE;
2518 if (IN_MULTICAST(ntohl(dst))) {
2520 * Send the reply on a known multicast capable vif.
2521 * If we don't have one, we can't source any multicasts anyway.
2523 if (phys_vif != -1) {
2524 IF_DEBUG(DEBUG_TRACE)
2525 dolog(LOG_DEBUG, 0, "Sending reply to %s from %s",
2526 inet_fmt(dst, s1), inet_fmt(uvifs[phys_vif].uv_lcl_addr, s2));
2527 k_set_ttl(qry->tr_rttl);
2528 send_igmp(uvifs[phys_vif].uv_lcl_addr, dst,
2529 resptype, no, group,
2533 dolog(LOG_INFO, 0, "No enabled phyints -- %s",
2534 "dropping traceroute reply");
2536 IF_DEBUG(DEBUG_TRACE)
2537 dolog(LOG_DEBUG, 0, "Sending %s to %s from %s",
2538 resptype == IGMP_MTRACE_RESP ? "reply" : "request on",
2539 inet_fmt(dst, s1), inet_fmt(src, s2));
2542 resptype, no, group,