3 Copyright (C) 2008 Everton da Silva Marques
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.
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.
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,
23 #include "zebra/rib.h"
35 #include "pim_iface.h"
37 #include "pim_zlookup.h"
38 #include "pim_upstream.h"
39 #include "pim_ifchannel.h"
40 #include "pim_neighbor.h"
42 #include "pim_zebra.h"
44 #include "pim_macro.h"
48 static void join_timer_start(struct pim_upstream
*up
);
49 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
);
51 void pim_upstream_free(struct pim_upstream
*up
)
53 XFREE(MTYPE_PIM_UPSTREAM
, up
);
56 static void upstream_channel_oil_detach(struct pim_upstream
*up
)
58 if (up
->channel_oil
) {
59 pim_channel_oil_del(up
->channel_oil
);
60 up
->channel_oil
= NULL
;
64 void pim_upstream_delete(struct pim_upstream
*up
)
66 THREAD_OFF(up
->t_join_timer
);
67 THREAD_OFF(up
->t_ka_timer
);
69 upstream_channel_oil_detach(up
);
72 notice that listnode_delete() can't be moved
73 into pim_upstream_free() because the later is
74 called by list_delete_all_node()
76 listnode_delete(qpim_upstream_list
, up
);
78 pim_upstream_free(up
);
81 static void send_join(struct pim_upstream
*up
)
83 zassert(up
->join_state
== PIM_UPSTREAM_JOINED
);
86 if (PIM_DEBUG_PIM_TRACE
) {
87 if (PIM_INADDR_IS_ANY(up
->rpf
.rpf_addr
)) {
91 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
92 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
93 pim_inet4_dump("<rpf?>", up
->rpf
.rpf_addr
, rpf_str
, sizeof(rpf_str
));
94 zlog_warn("%s: can't send join upstream: RPF'(%s,%s)=%s",
96 src_str
, grp_str
, rpf_str
);
101 /* send Join(S,G) to the current upstream neighbor */
102 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
109 static int on_join_timer(struct thread
*t
)
111 struct pim_upstream
*up
;
119 up
->t_join_timer
= NULL
;
120 join_timer_start(up
);
125 static void join_timer_start(struct pim_upstream
*up
)
127 if (PIM_DEBUG_PIM_EVENTS
) {
130 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
131 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
132 zlog_debug("%s: starting %d sec timer for upstream (S,G)=(%s,%s)",
138 zassert(!up
->t_join_timer
);
140 THREAD_TIMER_ON(master
, up
->t_join_timer
,
142 up
, qpim_t_periodic
);
145 void pim_upstream_join_timer_restart(struct pim_upstream
*up
)
147 THREAD_OFF(up
->t_join_timer
);
148 join_timer_start(up
);
151 static void pim_upstream_join_timer_restart_msec(struct pim_upstream
*up
,
154 if (PIM_DEBUG_PIM_EVENTS
) {
157 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
158 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
159 zlog_debug("%s: restarting %d msec timer for upstream (S,G)=(%s,%s)",
165 THREAD_OFF(up
->t_join_timer
);
166 THREAD_TIMER_MSEC_ON(master
, up
->t_join_timer
,
171 void pim_upstream_join_suppress(struct pim_upstream
*up
,
172 struct in_addr rpf_addr
,
175 long t_joinsuppress_msec
;
176 long join_timer_remain_msec
;
178 t_joinsuppress_msec
= MIN(pim_if_t_suppressed_msec(up
->rpf
.source_nexthop
.interface
),
181 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
183 if (PIM_DEBUG_PIM_TRACE
) {
187 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
188 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
189 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
190 zlog_debug("%s %s: detected Join(%s,%s) to RPF'(S,G)=%s: join_timer=%ld msec t_joinsuppress=%ld msec",
191 __FILE__
, __PRETTY_FUNCTION__
,
194 join_timer_remain_msec
, t_joinsuppress_msec
);
197 if (join_timer_remain_msec
< t_joinsuppress_msec
) {
198 if (PIM_DEBUG_PIM_TRACE
) {
201 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
202 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
203 zlog_debug("%s %s: suppressing Join(S,G)=(%s,%s) for %ld msec",
204 __FILE__
, __PRETTY_FUNCTION__
,
205 src_str
, grp_str
, t_joinsuppress_msec
);
208 pim_upstream_join_timer_restart_msec(up
, t_joinsuppress_msec
);
212 void pim_upstream_join_timer_decrease_to_t_override(const char *debug_label
,
213 struct pim_upstream
*up
,
214 struct in_addr rpf_addr
)
216 long join_timer_remain_msec
;
219 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
220 t_override_msec
= pim_if_t_override_msec(up
->rpf
.source_nexthop
.interface
);
222 if (PIM_DEBUG_PIM_TRACE
) {
226 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
227 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
228 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
229 zlog_debug("%s: to RPF'(%s,%s)=%s: join_timer=%ld msec t_override=%d msec",
231 src_str
, grp_str
, rpf_str
,
232 join_timer_remain_msec
, t_override_msec
);
235 if (join_timer_remain_msec
> t_override_msec
) {
236 if (PIM_DEBUG_PIM_TRACE
) {
239 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
240 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
241 zlog_debug("%s: decreasing (S,G)=(%s,%s) join timer to t_override=%d msec",
247 pim_upstream_join_timer_restart_msec(up
, t_override_msec
);
251 static void forward_on(struct pim_upstream
*up
)
253 struct listnode
*ifnode
;
254 struct listnode
*ifnextnode
;
255 struct listnode
*chnode
;
256 struct listnode
*chnextnode
;
257 struct interface
*ifp
;
258 struct pim_interface
*pim_ifp
;
259 struct pim_ifchannel
*ch
;
261 /* scan all interfaces */
262 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
267 /* scan per-interface (S,G) state */
268 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
270 if (ch
->upstream
!= up
)
273 if (pim_macro_chisin_oiflist(ch
))
274 pim_forward_start(ch
);
276 } /* scan iface channel list */
280 static void forward_off(struct pim_upstream
*up
)
282 struct listnode
*ifnode
;
283 struct listnode
*ifnextnode
;
284 struct listnode
*chnode
;
285 struct listnode
*chnextnode
;
286 struct interface
*ifp
;
287 struct pim_interface
*pim_ifp
;
288 struct pim_ifchannel
*ch
;
290 /* scan all interfaces */
291 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
296 /* scan per-interface (S,G) state */
297 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
299 if (ch
->upstream
!= up
)
302 pim_forward_stop(ch
);
304 } /* scan iface channel list */
308 static void pim_upstream_switch(struct pim_upstream
*up
,
309 enum pim_upstream_state new_state
)
311 enum pim_upstream_state old_state
= up
->join_state
;
313 zassert(old_state
!= new_state
);
315 up
->join_state
= new_state
;
316 up
->state_transition
= pim_time_monotonic_sec();
318 if (PIM_DEBUG_PIM_EVENTS
) {
321 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
322 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
323 zlog_debug("%s: PIM_UPSTREAM_%s: (S,G)=(%s,%s)",
325 ((new_state
== PIM_UPSTREAM_JOINED
) ? "JOINED" : "NOTJOINED"),
329 pim_upstream_update_assert_tracking_desired(up
);
331 if (new_state
== PIM_UPSTREAM_JOINED
) {
334 join_timer_start(up
);
338 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
343 zassert(up
->t_join_timer
);
344 THREAD_OFF(up
->t_join_timer
);
350 static struct pim_upstream
*pim_upstream_new(struct in_addr source_addr
,
351 struct in_addr group_addr
,
352 struct interface
*incoming
)
354 struct pim_upstream
*up
;
355 enum pim_rpf_result rpf_result
;
357 up
= XMALLOC(MTYPE_PIM_UPSTREAM
, sizeof(*up
));
359 zlog_err("%s: PIM XMALLOC(%zu) failure",
360 __PRETTY_FUNCTION__
, sizeof(*up
));
364 up
->source_addr
= source_addr
;
365 if (!pim_rp_set_upstream_addr (&up
->upstream_addr
, source_addr
))
367 if (PIM_DEBUG_PIM_TRACE
)
368 zlog_debug("%s: Received a (*,G) with no RP configured", __PRETTY_FUNCTION__
);
370 XFREE (MTYPE_PIM_UPSTREAM
, up
);
374 up
->group_addr
= group_addr
;
377 up
->t_join_timer
= NULL
;
378 up
->t_ka_timer
= NULL
;
380 up
->state_transition
= pim_time_monotonic_sec();
381 up
->channel_oil
= NULL
;
382 up
->sptbit
= PIM_UPSTREAM_SPTBIT_FALSE
;
384 up
->rpf
.source_nexthop
.interface
= 0;
385 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.s_addr
= PIM_NET_INADDR_ANY
;
386 up
->rpf
.source_nexthop
.mrib_metric_preference
= qpim_infinite_assert_metric
.metric_preference
;
387 up
->rpf
.source_nexthop
.mrib_route_metric
= qpim_infinite_assert_metric
.route_metric
;
388 up
->rpf
.rpf_addr
.s_addr
= PIM_NET_INADDR_ANY
;
390 rpf_result
= pim_rpf_update(up
, 0, incoming
);
391 if (rpf_result
== PIM_RPF_FAILURE
) {
392 XFREE(MTYPE_PIM_UPSTREAM
, up
);
396 listnode_add(qpim_upstream_list
, up
);
401 struct pim_upstream
*pim_upstream_find(struct in_addr source_addr
,
402 struct in_addr group_addr
)
404 struct listnode
*up_node
;
405 struct pim_upstream
*up
;
407 for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list
, up_node
, up
)) {
408 if (group_addr
.s_addr
== up
->group_addr
.s_addr
) {
409 if ((up
->source_addr
.s_addr
== INADDR_ANY
) ||
410 (source_addr
.s_addr
== up
->source_addr
.s_addr
)) {
419 struct pim_upstream
*pim_upstream_add(struct in_addr source_addr
,
420 struct in_addr group_addr
,
421 struct interface
*incoming
)
423 struct pim_upstream
*up
;
425 up
= pim_upstream_find(source_addr
, group_addr
);
430 up
= pim_upstream_new(source_addr
, group_addr
, incoming
);
436 void pim_upstream_del(struct pim_upstream
*up
)
440 if (up
->ref_count
< 1) {
441 pim_upstream_delete(up
);
446 Evaluate JoinDesired(S,G):
448 JoinDesired(S,G) is true if there is a downstream (S,G) interface I
451 inherited_olist(S,G) =
452 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
454 JoinDesired(S,G) may be affected by changes in the following:
456 pim_ifp->primary_address
458 ch->ifassert_winner_metric
460 ch->local_ifmembership
462 ch->upstream->rpf.source_nexthop.mrib_metric_preference
463 ch->upstream->rpf.source_nexthop.mrib_route_metric
464 ch->upstream->rpf.source_nexthop.interface
466 See also pim_upstream_update_join_desired() below.
468 int pim_upstream_evaluate_join_desired(struct pim_upstream
*up
)
470 struct listnode
*ifnode
;
471 struct listnode
*ifnextnode
;
472 struct listnode
*chnode
;
473 struct listnode
*chnextnode
;
474 struct interface
*ifp
;
475 struct pim_interface
*pim_ifp
;
476 struct pim_ifchannel
*ch
;
478 /* scan all interfaces */
479 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
484 /* scan per-interface (S,G) state */
485 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
486 if (ch
->upstream
!= up
)
489 if (pim_macro_ch_lost_assert(ch
))
490 continue; /* keep searching */
492 if (pim_macro_chisin_joins_or_include(ch
))
494 } /* scan iface channel list */
497 return 0; /* false */
501 See also pim_upstream_evaluate_join_desired() above.
503 void pim_upstream_update_join_desired(struct pim_upstream
*up
)
505 int was_join_desired
; /* boolean */
506 int is_join_desired
; /* boolean */
508 was_join_desired
= PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up
->flags
);
510 is_join_desired
= pim_upstream_evaluate_join_desired(up
);
512 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up
->flags
);
514 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up
->flags
);
516 /* switched from false to true */
517 if (is_join_desired
&& !was_join_desired
) {
518 zassert(up
->join_state
== PIM_UPSTREAM_NOTJOINED
);
519 pim_upstream_switch(up
, PIM_UPSTREAM_JOINED
);
523 /* switched from true to false */
524 if (!is_join_desired
&& was_join_desired
) {
525 zassert(up
->join_state
== PIM_UPSTREAM_JOINED
);
526 pim_upstream_switch(up
, PIM_UPSTREAM_NOTJOINED
);
532 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
533 Transitions from Joined State
534 RPF'(S,G) GenID changes
536 The upstream (S,G) state machine remains in Joined state. If the
537 Join Timer is set to expire in more than t_override seconds, reset
538 it so that it expires after t_override seconds.
540 void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr
)
542 struct listnode
*up_node
;
543 struct listnode
*up_nextnode
;
544 struct pim_upstream
*up
;
547 Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
549 for (ALL_LIST_ELEMENTS(qpim_upstream_list
, up_node
, up_nextnode
, up
)) {
551 if (PIM_DEBUG_PIM_TRACE
) {
555 char rpf_addr_str
[100];
556 pim_inet4_dump("<neigh?>", neigh_addr
, neigh_str
, sizeof(neigh_str
));
557 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
558 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
559 pim_inet4_dump("<rpf?>", up
->rpf
.rpf_addr
, rpf_addr_str
, sizeof(rpf_addr_str
));
560 zlog_debug("%s: matching neigh=%s against upstream (S,G)=(%s,%s) joined=%d rpf_addr=%s",
562 neigh_str
, src_str
, grp_str
,
563 up
->join_state
== PIM_UPSTREAM_JOINED
,
567 /* consider only (S,G) upstream in Joined state */
568 if (up
->join_state
!= PIM_UPSTREAM_JOINED
)
571 /* match RPF'(S,G)=neigh_addr */
572 if (up
->rpf
.rpf_addr
.s_addr
!= neigh_addr
.s_addr
)
575 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
581 void pim_upstream_rpf_interface_changed(struct pim_upstream
*up
,
582 struct interface
*old_rpf_ifp
)
584 struct listnode
*ifnode
;
585 struct listnode
*ifnextnode
;
586 struct interface
*ifp
;
588 /* scan all interfaces */
589 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
590 struct listnode
*chnode
;
591 struct listnode
*chnextnode
;
592 struct pim_ifchannel
*ch
;
593 struct pim_interface
*pim_ifp
;
599 /* search all ifchannels */
600 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
601 if (ch
->upstream
!= up
)
604 if (ch
->ifassert_state
== PIM_IFASSERT_I_AM_LOSER
) {
606 /* RPF_interface(S) was NOT I */
607 (old_rpf_ifp
== ch
->interface
)
609 /* RPF_interface(S) stopped being I */
610 (ch
->upstream
->rpf
.source_nexthop
.interface
!= ch
->interface
)
612 assert_action_a5(ch
);
614 } /* PIM_IFASSERT_I_AM_LOSER */
616 pim_ifchannel_update_assert_tracking_desired(ch
);
621 void pim_upstream_update_could_assert(struct pim_upstream
*up
)
623 struct listnode
*ifnode
;
624 struct listnode
*ifnextnode
;
625 struct listnode
*chnode
;
626 struct listnode
*chnextnode
;
627 struct interface
*ifp
;
628 struct pim_interface
*pim_ifp
;
629 struct pim_ifchannel
*ch
;
631 /* scan all interfaces */
632 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
637 /* scan per-interface (S,G) state */
638 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
640 if (ch
->upstream
!= up
)
643 pim_ifchannel_update_could_assert(ch
);
645 } /* scan iface channel list */
649 void pim_upstream_update_my_assert_metric(struct pim_upstream
*up
)
651 struct listnode
*ifnode
;
652 struct listnode
*ifnextnode
;
653 struct listnode
*chnode
;
654 struct listnode
*chnextnode
;
655 struct interface
*ifp
;
656 struct pim_interface
*pim_ifp
;
657 struct pim_ifchannel
*ch
;
659 /* scan all interfaces */
660 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
665 /* scan per-interface (S,G) state */
666 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
668 if (ch
->upstream
!= up
)
671 pim_ifchannel_update_my_assert_metric(ch
);
673 } /* scan iface channel list */
677 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
)
679 struct listnode
*ifnode
;
680 struct listnode
*ifnextnode
;
681 struct listnode
*chnode
;
682 struct listnode
*chnextnode
;
683 struct interface
*ifp
;
684 struct pim_interface
*pim_ifp
;
685 struct pim_ifchannel
*ch
;
687 /* scan all interfaces */
688 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
693 /* scan per-interface (S,G) state */
694 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
696 if (ch
->upstream
!= up
)
699 pim_ifchannel_update_assert_tracking_desired(ch
);
701 } /* scan iface channel list */
706 * On an RP, the PMBR value must be cleared when the
707 * Keepalive Timer expires
710 pim_upstream_keep_alive_timer (struct thread
*t
)
712 struct pim_upstream
*up
;
716 if (I_am_RP (up
->group_addr
))
718 pim_br_clear_pmbr (up
->source_addr
, up
->group_addr
);
720 * We need to do more here :)
721 * But this is the start.
726 pim_mroute_update_counters (up
->channel_oil
);
728 if (up
->channel_oil
->cc
.oldpktcnt
>= up
->channel_oil
->cc
.pktcnt
)
730 pim_mroute_del (up
->channel_oil
);
731 pim_upstream_delete (up
);
735 up
->t_ka_timer
= NULL
;
736 pim_upstream_keep_alive_timer_start (up
, PIM_KEEPALIVE_PERIOD
);
743 pim_upstream_keep_alive_timer_start (struct pim_upstream
*up
,
746 THREAD_TIMER_ON (master
,
748 pim_upstream_keep_alive_timer
,
753 * 4.2.1 Last-Hop Switchover to the SPT
755 * In Sparse-Mode PIM, last-hop routers join the shared tree towards the
756 * RP. Once traffic from sources to joined groups arrives at a last-hop
757 * router, it has the option of switching to receive the traffic on a
758 * shortest path tree (SPT).
760 * The decision for a router to switch to the SPT is controlled as
764 * CheckSwitchToSpt(S,G) {
765 * if ( ( pim_include(*,G) (-) pim_exclude(S,G)
766 * (+) pim_include(S,G) != NULL )
767 * AND SwitchToSptDesired(S,G) ) {
768 * # Note: Restarting the KAT will result in the SPT switch
769 * set KeepaliveTimer(S,G) to Keepalive_Period
773 * SwitchToSptDesired(S,G) is a policy function that is implementation
774 * defined. An "infinite threshold" policy can be implemented by making
775 * SwitchToSptDesired(S,G) return false all the time. A "switch on
776 * first packet" policy can be implemented by making
777 * SwitchToSptDesired(S,G) return true once a single packet has been
778 * received for the source and group.
781 pim_upstream_switch_to_spt_desired (struct in_addr source
, struct in_addr group
)