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