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