1/* 2 PIM for Quagga 3 Copyright (C) 2008 Everton da Silva Marques 4 5 This program is free software; you can redistribute it and/or modify 6 it under the terms of the GNU General Public License as published by 7 the Free Software Foundation; either version 2 of the License, or 8 (at your option) any later version. 9 10 This program is distributed in the hope that it will be useful, but 11 WITHOUT ANY WARRANTY; without even the implied warranty of 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 General Public License for more details. 14 15 You should have received a copy of the GNU General Public License 16 along with this program; see the file COPYING; if not, write to the 17 Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, 18 MA 02110-1301 USA 19 20 $QuaggaId: $Format:%an, %ai, %h$ $ 21*/ 22 23#include <zebra.h> 24 25#include "zebra/rib.h" 26 27#include "log.h" 28#include "zclient.h" 29#include "memory.h" 30#include "thread.h" 31#include "linklist.h" 32 33#include "pimd.h" 34#include "pim_pim.h" 35#include "pim_str.h" 36#include "pim_time.h" 37#include "pim_iface.h" 38#include "pim_join.h" 39#include "pim_zlookup.h" 40#include "pim_upstream.h" 41#include "pim_ifchannel.h" 42#include "pim_neighbor.h" 43#include "pim_rpf.h" 44#include "pim_zebra.h" 45#include "pim_oil.h" 46#include "pim_macro.h" 47 48static void join_timer_start(struct pim_upstream *up); 49static void pim_upstream_update_assert_tracking_desired(struct pim_upstream *up); 50 51void pim_upstream_free(struct pim_upstream *up) 52{ 53 XFREE(MTYPE_PIM_UPSTREAM, up); 54} 55 56static void upstream_channel_oil_detach(struct pim_upstream *up) 57{ 58 if (up->channel_oil) { 59 pim_channel_oil_del(up->channel_oil); 60 up->channel_oil = 0; 61 } 62} 63 64void pim_upstream_delete(struct pim_upstream *up) 65{ 66 THREAD_OFF(up->t_join_timer); 67 68 upstream_channel_oil_detach(up); 69 70 /* 71 notice that listnode_delete() can't be moved 72 into pim_upstream_free() because the later is 73 called by list_delete_all_node() 74 */ 75 listnode_delete(qpim_upstream_list, up); 76 77 pim_upstream_free(up); 78} 79 80static void send_join(struct pim_upstream *up) 81{ 82 zassert(up->join_state == PIM_UPSTREAM_JOINED); 83 84 85 if (PIM_DEBUG_PIM_TRACE) { 86 if (PIM_INADDR_IS_ANY(up->rpf.rpf_addr)) { 87 char src_str[100]; 88 char grp_str[100]; 89 char rpf_str[100]; 90 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 91 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 92 pim_inet4_dump("<rpf?>", up->rpf.rpf_addr, rpf_str, sizeof(rpf_str)); 93 zlog_warn("%s: can't send join upstream: RPF'(%s,%s)=%s", 94 __PRETTY_FUNCTION__, 95 src_str, grp_str, rpf_str); 96 /* warning only */ 97 } 98 } 99 100 /* send Join(S,G) to the current upstream neighbor */ 101 pim_joinprune_send(up->rpf.source_nexthop.interface, 102 up->rpf.rpf_addr, 103 up->source_addr, 104 up->group_addr, 105 1 /* join */); 106} 107 108static int on_join_timer(struct thread *t) 109{ 110 struct pim_upstream *up; 111 112 zassert(t); 113 up = THREAD_ARG(t); 114 zassert(up); 115 116 send_join(up); 117 118 up->t_join_timer = 0; 119 join_timer_start(up); 120 121 return 0; 122} 123 124static void join_timer_start(struct pim_upstream *up) 125{ 126 if (PIM_DEBUG_PIM_EVENTS) { 127 char src_str[100]; 128 char grp_str[100]; 129 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 130 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 131 zlog_debug("%s: starting %d sec timer for upstream (S,G)=(%s,%s)", 132 __PRETTY_FUNCTION__, 133 qpim_t_periodic, 134 src_str, grp_str); 135 } 136 137 zassert(!up->t_join_timer); 138 139 THREAD_TIMER_ON(master, up->t_join_timer, 140 on_join_timer, 141 up, qpim_t_periodic); 142} 143 144void pim_upstream_join_timer_restart(struct pim_upstream *up) 145{ 146 THREAD_OFF(up->t_join_timer); 147 join_timer_start(up); 148} 149 150static void pim_upstream_join_timer_restart_msec(struct pim_upstream *up, 151 int interval_msec) 152{ 153 if (PIM_DEBUG_PIM_EVENTS) { 154 char src_str[100]; 155 char grp_str[100]; 156 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 157 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 158 zlog_debug("%s: restarting %d msec timer for upstream (S,G)=(%s,%s)", 159 __PRETTY_FUNCTION__, 160 interval_msec, 161 src_str, grp_str); 162 } 163 164 THREAD_OFF(up->t_join_timer); 165 THREAD_TIMER_MSEC_ON(master, up->t_join_timer, 166 on_join_timer, 167 up, interval_msec); 168} 169 170void pim_upstream_join_suppress(struct pim_upstream *up, 171 struct in_addr rpf_addr, 172 int holdtime) 173{ 174 long t_joinsuppress_msec; 175 long join_timer_remain_msec; 176 177 t_joinsuppress_msec = MIN(pim_if_t_suppressed_msec(up->rpf.source_nexthop.interface), 178 1000 * holdtime); 179 180 join_timer_remain_msec = pim_time_timer_remain_msec(up->t_join_timer); 181 182 if (PIM_DEBUG_PIM_TRACE) { 183 char src_str[100]; 184 char grp_str[100]; 185 char rpf_str[100]; 186 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 187 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 188 pim_inet4_dump("<rpf?>", rpf_addr, rpf_str, sizeof(rpf_str)); 189 zlog_debug("%s %s: detected Join(%s,%s) to RPF'(S,G)=%s: join_timer=%ld msec t_joinsuppress=%ld msec", 190 __FILE__, __PRETTY_FUNCTION__, 191 src_str, grp_str, 192 rpf_str, 193 join_timer_remain_msec, t_joinsuppress_msec); 194 } 195 196 if (join_timer_remain_msec < t_joinsuppress_msec) { 197 if (PIM_DEBUG_PIM_TRACE) { 198 char src_str[100]; 199 char grp_str[100]; 200 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 201 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 202 zlog_debug("%s %s: suppressing Join(S,G)=(%s,%s) for %ld msec", 203 __FILE__, __PRETTY_FUNCTION__, 204 src_str, grp_str, t_joinsuppress_msec); 205 } 206 207 pim_upstream_join_timer_restart_msec(up, t_joinsuppress_msec); 208 } 209} 210 211void pim_upstream_join_timer_decrease_to_t_override(const char *debug_label, 212 struct pim_upstream *up, 213 struct in_addr rpf_addr) 214{ 215 long join_timer_remain_msec; 216 int t_override_msec; 217 218 join_timer_remain_msec = pim_time_timer_remain_msec(up->t_join_timer); 219 t_override_msec = pim_if_t_override_msec(up->rpf.source_nexthop.interface); 220 221 if (PIM_DEBUG_PIM_TRACE) { 222 char src_str[100]; 223 char grp_str[100]; 224 char rpf_str[100]; 225 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 226 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 227 pim_inet4_dump("<rpf?>", rpf_addr, rpf_str, sizeof(rpf_str)); 228 zlog_debug("%s: to RPF'(%s,%s)=%s: join_timer=%ld msec t_override=%d msec", 229 debug_label, 230 src_str, grp_str, rpf_str, 231 join_timer_remain_msec, t_override_msec); 232 } 233 234 if (join_timer_remain_msec > t_override_msec) { 235 if (PIM_DEBUG_PIM_TRACE) { 236 char src_str[100]; 237 char grp_str[100]; 238 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 239 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 240 zlog_debug("%s: decreasing (S,G)=(%s,%s) join timer to t_override=%d msec", 241 debug_label, 242 src_str, grp_str, 243 t_override_msec); 244 } 245 246 pim_upstream_join_timer_restart_msec(up, t_override_msec); 247 } 248} 249 250static void forward_on(struct pim_upstream *up) 251{ 252 struct listnode *ifnode; 253 struct listnode *ifnextnode; 254 struct listnode *chnode; 255 struct listnode *chnextnode; 256 struct interface *ifp; 257 struct pim_interface *pim_ifp; 258 struct pim_ifchannel *ch; 259 260 /* scan all interfaces */ 261 for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) { 262 pim_ifp = ifp->info; 263 if (!pim_ifp) 264 continue; 265 266 /* scan per-interface (S,G) state */ 267 for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) { 268 269 if (ch->upstream != up) 270 continue; 271 272 if (pim_macro_chisin_oiflist(ch)) 273 pim_forward_start(ch); 274 275 } /* scan iface channel list */ 276 } /* scan iflist */ 277} 278 279static void forward_off(struct pim_upstream *up) 280{ 281 struct listnode *ifnode; 282 struct listnode *ifnextnode; 283 struct listnode *chnode; 284 struct listnode *chnextnode; 285 struct interface *ifp; 286 struct pim_interface *pim_ifp; 287 struct pim_ifchannel *ch; 288 289 /* scan all interfaces */ 290 for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) { 291 pim_ifp = ifp->info; 292 if (!pim_ifp) 293 continue; 294 295 /* scan per-interface (S,G) state */ 296 for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) { 297 298 if (ch->upstream != up) 299 continue; 300 301 pim_forward_stop(ch); 302 303 } /* scan iface channel list */ 304 } /* scan iflist */ 305} 306 307static void pim_upstream_switch(struct pim_upstream *up, 308 enum pim_upstream_state new_state) 309{ 310 enum pim_upstream_state old_state = up->join_state; 311 312 zassert(old_state != new_state); 313 314 up->join_state = new_state; 315 up->state_transition = pim_time_monotonic_sec(); 316 317 if (PIM_DEBUG_PIM_EVENTS) { 318 char src_str[100]; 319 char grp_str[100]; 320 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 321 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 322 zlog_debug("%s: PIM_UPSTREAM_%s: (S,G)=(%s,%s)", 323 __PRETTY_FUNCTION__, 324 ((new_state == PIM_UPSTREAM_JOINED) ? "JOINED" : "NOTJOINED"), 325 src_str, grp_str); 326 } 327 328 pim_upstream_update_assert_tracking_desired(up); 329 330 if (new_state == PIM_UPSTREAM_JOINED) { 331 forward_on(up); 332 send_join(up); 333 join_timer_start(up); 334 } 335 else { 336 forward_off(up); 337 pim_joinprune_send(up->rpf.source_nexthop.interface, 338 up->rpf.rpf_addr, 339 up->source_addr, 340 up->group_addr, 341 0 /* prune */); 342 zassert(up->t_join_timer); 343 THREAD_OFF(up->t_join_timer); 344 } 345 346} 347 348static struct pim_upstream *pim_upstream_new(struct in_addr source_addr, 349 struct in_addr group_addr) 350{ 351 struct pim_upstream *up; 352 353 up = XMALLOC(MTYPE_PIM_UPSTREAM, sizeof(*up)); 354 if (!up) { 355 zlog_err("%s: PIM XMALLOC(%zu) failure", 356 __PRETTY_FUNCTION__, sizeof(*up)); 357 return 0; 358 } 359 360 up->source_addr = source_addr; 361 up->group_addr = group_addr; 362 up->flags = 0; 363 up->ref_count = 1; 364 up->t_join_timer = 0; 365 up->join_state = 0; 366 up->state_transition = pim_time_monotonic_sec(); 367 up->channel_oil = 0; 368 369 up->rpf.source_nexthop.interface = 0; 370 up->rpf.source_nexthop.mrib_nexthop_addr.s_addr = PIM_NET_INADDR_ANY; 371 up->rpf.source_nexthop.mrib_metric_preference = qpim_infinite_assert_metric.metric_preference; 372 up->rpf.source_nexthop.mrib_route_metric = qpim_infinite_assert_metric.route_metric; 373 up->rpf.rpf_addr.s_addr = PIM_NET_INADDR_ANY; 374 375 pim_rpf_update(up, 0); 376 377 listnode_add(qpim_upstream_list, up); 378 379 return up; 380} 381 382struct pim_upstream *pim_upstream_find(struct in_addr source_addr, 383 struct in_addr group_addr) 384{ 385 struct listnode *up_node; 386 struct pim_upstream *up; 387 388 for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list, up_node, up)) { 389 if ( 390 (source_addr.s_addr == up->source_addr.s_addr) && 391 (group_addr.s_addr == up->group_addr.s_addr) 392 ) { 393 return up; 394 } 395 } 396 397 return 0; 398} 399 400struct pim_upstream *pim_upstream_add(struct in_addr source_addr, 401 struct in_addr group_addr) 402{ 403 struct pim_upstream *up; 404 405 up = pim_upstream_find(source_addr, group_addr); 406 if (up) { 407 ++up->ref_count; 408 } 409 else { 410 up = pim_upstream_new(source_addr, group_addr); 411 } 412 413 return up; 414} 415 416void pim_upstream_del(struct pim_upstream *up) 417{ 418 --up->ref_count; 419 420 if (up->ref_count < 1) { 421 pim_upstream_delete(up); 422 } 423} 424 425/* 426 Evaluate JoinDesired(S,G): 427 428 JoinDesired(S,G) is true if there is a downstream (S,G) interface I 429 in the set: 430 431 inherited_olist(S,G) = 432 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G) 433 434 JoinDesired(S,G) may be affected by changes in the following: 435 436 pim_ifp->primary_address 437 pim_ifp->pim_dr_addr 438 ch->ifassert_winner_metric 439 ch->ifassert_winner 440 ch->local_ifmembership 441 ch->ifjoin_state 442 ch->upstream->rpf.source_nexthop.mrib_metric_preference 443 ch->upstream->rpf.source_nexthop.mrib_route_metric 444 ch->upstream->rpf.source_nexthop.interface 445 446 See also pim_upstream_update_join_desired() below. 447 */ 448int pim_upstream_evaluate_join_desired(struct pim_upstream *up) 449{ 450 struct listnode *ifnode; 451 struct listnode *ifnextnode; 452 struct listnode *chnode; 453 struct listnode *chnextnode; 454 struct interface *ifp; 455 struct pim_interface *pim_ifp; 456 struct pim_ifchannel *ch; 457 458 /* scan all interfaces */ 459 for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) { 460 pim_ifp = ifp->info; 461 if (!pim_ifp) 462 continue; 463 464 /* scan per-interface (S,G) state */ 465 for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) { 466 if (ch->upstream != up) 467 continue; 468 469 if (pim_macro_ch_lost_assert(ch)) 470 continue; /* keep searching */ 471 472 if (pim_macro_chisin_joins_or_include(ch)) 473 return 1; /* true */ 474 } /* scan iface channel list */ 475 } /* scan iflist */ 476 477 return 0; /* false */ 478} 479 480/* 481 See also pim_upstream_evaluate_join_desired() above. 482*/ 483void pim_upstream_update_join_desired(struct pim_upstream *up) 484{ 485 int was_join_desired; /* boolean */ 486 int is_join_desired; /* boolean */ 487 488 was_join_desired = PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up->flags); 489 490 is_join_desired = pim_upstream_evaluate_join_desired(up); 491 if (is_join_desired) 492 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up->flags); 493 else 494 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up->flags); 495 496 /* switched from false to true */ 497 if (is_join_desired && !was_join_desired) { 498 zassert(up->join_state == PIM_UPSTREAM_NOTJOINED); 499 pim_upstream_switch(up, PIM_UPSTREAM_JOINED); 500 return; 501 } 502 503 /* switched from true to false */ 504 if (!is_join_desired && was_join_desired) { 505 zassert(up->join_state == PIM_UPSTREAM_JOINED); 506 pim_upstream_switch(up, PIM_UPSTREAM_NOTJOINED); 507 return; 508 } 509} 510 511/* 512 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages 513 Transitions from Joined State 514 RPF'(S,G) GenID changes 515 516 The upstream (S,G) state machine remains in Joined state. If the 517 Join Timer is set to expire in more than t_override seconds, reset 518 it so that it expires after t_override seconds. 519*/ 520void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr) 521{ 522 struct listnode *up_node; 523 struct listnode *up_nextnode; 524 struct pim_upstream *up; 525 526 /* 527 Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr 528 */ 529 for (ALL_LIST_ELEMENTS(qpim_upstream_list, up_node, up_nextnode, up)) { 530 531 if (PIM_DEBUG_PIM_TRACE) { 532 char neigh_str[100]; 533 char src_str[100]; 534 char grp_str[100]; 535 char rpf_addr_str[100]; 536 pim_inet4_dump("<neigh?>", neigh_addr, neigh_str, sizeof(neigh_str)); 537 pim_inet4_dump("<src?>", up->source_addr, src_str, sizeof(src_str)); 538 pim_inet4_dump("<grp?>", up->group_addr, grp_str, sizeof(grp_str)); 539 pim_inet4_dump("<rpf?>", up->rpf.rpf_addr, rpf_addr_str, sizeof(rpf_addr_str)); 540 zlog_debug("%s: matching neigh=%s against upstream (S,G)=(%s,%s) joined=%d rpf_addr=%s", 541 __PRETTY_FUNCTION__, 542 neigh_str, src_str, grp_str, 543 up->join_state == PIM_UPSTREAM_JOINED, 544 rpf_addr_str); 545 } 546 547 /* consider only (S,G) upstream in Joined state */ 548 if (up->join_state != PIM_UPSTREAM_JOINED) 549 continue; 550 551 /* match RPF'(S,G)=neigh_addr */ 552 if (up->rpf.rpf_addr.s_addr != neigh_addr.s_addr) 553 continue; 554 555 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change", 556 up, neigh_addr); 557 } 558} 559 560 561void pim_upstream_rpf_interface_changed(struct pim_upstream *up, 562 struct interface *old_rpf_ifp) 563{ 564 struct listnode *ifnode; 565 struct listnode *ifnextnode; 566 struct interface *ifp; 567 568 /* scan all interfaces */ 569 for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) { 570 struct listnode *chnode; 571 struct listnode *chnextnode; 572 struct pim_ifchannel *ch; 573 struct pim_interface *pim_ifp; 574 575 pim_ifp = ifp->info; 576 if (!pim_ifp) 577 continue; 578 579 /* search all ifchannels */ 580 for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) { 581 if (ch->upstream != up) 582 continue; 583 584 if (ch->ifassert_state == PIM_IFASSERT_I_AM_LOSER) { 585 if ( 586 /* RPF_interface(S) was NOT I */ 587 (old_rpf_ifp == ch->interface) 588 && 589 /* RPF_interface(S) stopped being I */ 590 (ch->upstream->rpf.source_nexthop.interface != ch->interface) 591 ) { 592 assert_action_a5(ch); 593 } 594 } /* PIM_IFASSERT_I_AM_LOSER */ 595 596 pim_ifchannel_update_assert_tracking_desired(ch); 597 } 598 } 599} 600 601void pim_upstream_update_could_assert(struct pim_upstream *up) 602{ 603 struct listnode *ifnode; 604 struct listnode *ifnextnode; 605 struct listnode *chnode; 606 struct listnode *chnextnode; 607 struct interface *ifp; 608 struct pim_interface *pim_ifp; 609 struct pim_ifchannel *ch; 610 611 /* scan all interfaces */ 612 for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) { 613 pim_ifp = ifp->info; 614 if (!pim_ifp) 615 continue; 616 617 /* scan per-interface (S,G) state */ 618 for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) { 619 620 if (ch->upstream != up) 621 continue; 622 623 pim_ifchannel_update_could_assert(ch); 624 625 } /* scan iface channel list */ 626 } /* scan iflist */ 627} 628 629void pim_upstream_update_my_assert_metric(struct pim_upstream *up) 630{ 631 struct listnode *ifnode; 632 struct listnode *ifnextnode; 633 struct listnode *chnode; 634 struct listnode *chnextnode; 635 struct interface *ifp; 636 struct pim_interface *pim_ifp; 637 struct pim_ifchannel *ch; 638 639 /* scan all interfaces */ 640 for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) { 641 pim_ifp = ifp->info; 642 if (!pim_ifp) 643 continue; 644 645 /* scan per-interface (S,G) state */ 646 for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) { 647 648 if (ch->upstream != up) 649 continue; 650 651 pim_ifchannel_update_my_assert_metric(ch); 652 653 } /* scan iface channel list */ 654 } /* scan iflist */ 655} 656 657static void pim_upstream_update_assert_tracking_desired(struct pim_upstream *up) 658{ 659 struct listnode *ifnode; 660 struct listnode *ifnextnode; 661 struct listnode *chnode; 662 struct listnode *chnextnode; 663 struct interface *ifp; 664 struct pim_interface *pim_ifp; 665 struct pim_ifchannel *ch; 666 667 /* scan all interfaces */ 668 for (ALL_LIST_ELEMENTS(iflist, ifnode, ifnextnode, ifp)) { 669 pim_ifp = ifp->info; 670 if (!pim_ifp) 671 continue; 672 673 /* scan per-interface (S,G) state */ 674 for (ALL_LIST_ELEMENTS(pim_ifp->pim_ifchannel_list, chnode, chnextnode, ch)) { 675 676 if (ch->upstream != up) 677 continue; 678 679 pim_ifchannel_update_assert_tracking_desired(ch); 680 681 } /* scan iface channel list */ 682 } /* scan iflist */ 683} 684