Annotation of embedaddon/mrouted/prune.c, revision 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