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,
20 $QuaggaId: $Format:%an, %ai, %h$ $
25 #include "zebra/rib.h"
37 #include "pim_iface.h"
39 #include "pim_zlookup.h"
40 #include "pim_upstream.h"
41 #include "pim_ifchannel.h"
42 #include "pim_neighbor.h"
44 #include "pim_zebra.h"
46 #include "pim_macro.h"
50 static void join_timer_start(struct pim_upstream
*up
);
51 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
);
53 void pim_upstream_free(struct pim_upstream
*up
)
55 XFREE(MTYPE_PIM_UPSTREAM
, up
);
58 static void upstream_channel_oil_detach(struct pim_upstream
*up
)
60 if (up
->channel_oil
) {
61 pim_channel_oil_del(up
->channel_oil
);
62 up
->channel_oil
= NULL
;
66 void pim_upstream_delete(struct pim_upstream
*up
)
68 THREAD_OFF(up
->t_join_timer
);
69 THREAD_OFF(up
->t_ka_timer
);
71 upstream_channel_oil_detach(up
);
74 notice that listnode_delete() can't be moved
75 into pim_upstream_free() because the later is
76 called by list_delete_all_node()
78 listnode_delete(qpim_upstream_list
, up
);
80 pim_upstream_free(up
);
83 static void send_join(struct pim_upstream
*up
)
85 zassert(up
->join_state
== PIM_UPSTREAM_JOINED
);
88 if (PIM_DEBUG_PIM_TRACE
) {
89 if (PIM_INADDR_IS_ANY(up
->rpf
.rpf_addr
)) {
93 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
94 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
95 pim_inet4_dump("<rpf?>", up
->rpf
.rpf_addr
, rpf_str
, sizeof(rpf_str
));
96 zlog_warn("%s: can't send join upstream: RPF'(%s,%s)=%s",
98 src_str
, grp_str
, rpf_str
);
103 /* send Join(S,G) to the current upstream neighbor */
104 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
111 static int on_join_timer(struct thread
*t
)
113 struct pim_upstream
*up
;
121 up
->t_join_timer
= NULL
;
122 join_timer_start(up
);
127 static void join_timer_start(struct pim_upstream
*up
)
129 if (PIM_DEBUG_PIM_EVENTS
) {
132 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
133 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
134 zlog_debug("%s: starting %d sec timer for upstream (S,G)=(%s,%s)",
140 zassert(!up
->t_join_timer
);
142 THREAD_TIMER_ON(master
, up
->t_join_timer
,
144 up
, qpim_t_periodic
);
147 void pim_upstream_join_timer_restart(struct pim_upstream
*up
)
149 THREAD_OFF(up
->t_join_timer
);
150 join_timer_start(up
);
153 static void pim_upstream_join_timer_restart_msec(struct pim_upstream
*up
,
156 if (PIM_DEBUG_PIM_EVENTS
) {
159 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
160 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
161 zlog_debug("%s: restarting %d msec timer for upstream (S,G)=(%s,%s)",
167 THREAD_OFF(up
->t_join_timer
);
168 THREAD_TIMER_MSEC_ON(master
, up
->t_join_timer
,
173 void pim_upstream_join_suppress(struct pim_upstream
*up
,
174 struct in_addr rpf_addr
,
177 long t_joinsuppress_msec
;
178 long join_timer_remain_msec
;
180 t_joinsuppress_msec
= MIN(pim_if_t_suppressed_msec(up
->rpf
.source_nexthop
.interface
),
183 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
185 if (PIM_DEBUG_PIM_TRACE
) {
189 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
190 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
191 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
192 zlog_debug("%s %s: detected Join(%s,%s) to RPF'(S,G)=%s: join_timer=%ld msec t_joinsuppress=%ld msec",
193 __FILE__
, __PRETTY_FUNCTION__
,
196 join_timer_remain_msec
, t_joinsuppress_msec
);
199 if (join_timer_remain_msec
< t_joinsuppress_msec
) {
200 if (PIM_DEBUG_PIM_TRACE
) {
203 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
204 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
205 zlog_debug("%s %s: suppressing Join(S,G)=(%s,%s) for %ld msec",
206 __FILE__
, __PRETTY_FUNCTION__
,
207 src_str
, grp_str
, t_joinsuppress_msec
);
210 pim_upstream_join_timer_restart_msec(up
, t_joinsuppress_msec
);
214 void pim_upstream_join_timer_decrease_to_t_override(const char *debug_label
,
215 struct pim_upstream
*up
,
216 struct in_addr rpf_addr
)
218 long join_timer_remain_msec
;
221 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
222 t_override_msec
= pim_if_t_override_msec(up
->rpf
.source_nexthop
.interface
);
224 if (PIM_DEBUG_PIM_TRACE
) {
228 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
229 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
230 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
231 zlog_debug("%s: to RPF'(%s,%s)=%s: join_timer=%ld msec t_override=%d msec",
233 src_str
, grp_str
, rpf_str
,
234 join_timer_remain_msec
, t_override_msec
);
237 if (join_timer_remain_msec
> t_override_msec
) {
238 if (PIM_DEBUG_PIM_TRACE
) {
241 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
242 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
243 zlog_debug("%s: decreasing (S,G)=(%s,%s) join timer to t_override=%d msec",
249 pim_upstream_join_timer_restart_msec(up
, t_override_msec
);
253 static void forward_on(struct pim_upstream
*up
)
255 struct listnode
*ifnode
;
256 struct listnode
*ifnextnode
;
257 struct listnode
*chnode
;
258 struct listnode
*chnextnode
;
259 struct interface
*ifp
;
260 struct pim_interface
*pim_ifp
;
261 struct pim_ifchannel
*ch
;
263 /* scan all interfaces */
264 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
269 /* scan per-interface (S,G) state */
270 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
272 if (ch
->upstream
!= up
)
275 if (pim_macro_chisin_oiflist(ch
))
276 pim_forward_start(ch
);
278 } /* scan iface channel list */
282 static void forward_off(struct pim_upstream
*up
)
284 struct listnode
*ifnode
;
285 struct listnode
*ifnextnode
;
286 struct listnode
*chnode
;
287 struct listnode
*chnextnode
;
288 struct interface
*ifp
;
289 struct pim_interface
*pim_ifp
;
290 struct pim_ifchannel
*ch
;
292 /* scan all interfaces */
293 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
298 /* scan per-interface (S,G) state */
299 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
301 if (ch
->upstream
!= up
)
304 pim_forward_stop(ch
);
306 } /* scan iface channel list */
310 static void pim_upstream_switch(struct pim_upstream
*up
,
311 enum pim_upstream_state new_state
)
313 enum pim_upstream_state old_state
= up
->join_state
;
315 zassert(old_state
!= new_state
);
317 up
->join_state
= new_state
;
318 up
->state_transition
= pim_time_monotonic_sec();
320 if (PIM_DEBUG_PIM_EVENTS
) {
323 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
324 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
325 zlog_debug("%s: PIM_UPSTREAM_%s: (S,G)=(%s,%s)",
327 ((new_state
== PIM_UPSTREAM_JOINED
) ? "JOINED" : "NOTJOINED"),
331 pim_upstream_update_assert_tracking_desired(up
);
333 if (new_state
== PIM_UPSTREAM_JOINED
) {
336 join_timer_start(up
);
340 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
345 zassert(up
->t_join_timer
);
346 THREAD_OFF(up
->t_join_timer
);
352 static struct pim_upstream
*pim_upstream_new(struct in_addr source_addr
,
353 struct in_addr group_addr
,
354 struct interface
*incoming
)
356 struct pim_upstream
*up
;
357 enum pim_rpf_result rpf_result
;
359 up
= XMALLOC(MTYPE_PIM_UPSTREAM
, sizeof(*up
));
361 zlog_err("%s: PIM XMALLOC(%zu) failure",
362 __PRETTY_FUNCTION__
, sizeof(*up
));
366 up
->source_addr
= source_addr
;
367 if (!pim_rp_set_upstream_addr (&up
->upstream_addr
, source_addr
))
369 if (PIM_DEBUG_PIM_TRACE
)
370 zlog_debug("%s: Received a (*,G) with no RP configured", __PRETTY_FUNCTION__
);
372 XFREE (MTYPE_PIM_UPSTREAM
, up
);
376 up
->group_addr
= group_addr
;
379 up
->t_join_timer
= NULL
;
380 up
->t_ka_timer
= NULL
;
382 up
->state_transition
= pim_time_monotonic_sec();
383 up
->channel_oil
= NULL
;
384 up
->sptbit
= PIM_UPSTREAM_SPTBIT_FALSE
;
386 up
->rpf
.source_nexthop
.interface
= 0;
387 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.s_addr
= PIM_NET_INADDR_ANY
;
388 up
->rpf
.source_nexthop
.mrib_metric_preference
= qpim_infinite_assert_metric
.metric_preference
;
389 up
->rpf
.source_nexthop
.mrib_route_metric
= qpim_infinite_assert_metric
.route_metric
;
390 up
->rpf
.rpf_addr
.s_addr
= PIM_NET_INADDR_ANY
;
392 rpf_result
= pim_rpf_update(up
, 0, incoming
);
393 if (rpf_result
== PIM_RPF_FAILURE
) {
394 XFREE(MTYPE_PIM_UPSTREAM
, up
);
398 listnode_add(qpim_upstream_list
, up
);
403 struct pim_upstream
*pim_upstream_find(struct in_addr source_addr
,
404 struct in_addr group_addr
)
406 struct listnode
*up_node
;
407 struct pim_upstream
*up
;
409 for (ALL_LIST_ELEMENTS_RO(qpim_upstream_list
, up_node
, up
)) {
410 if (group_addr
.s_addr
== up
->group_addr
.s_addr
) {
411 if ((up
->source_addr
.s_addr
== INADDR_ANY
) ||
412 (source_addr
.s_addr
== up
->source_addr
.s_addr
)) {
421 struct pim_upstream
*pim_upstream_add(struct in_addr source_addr
,
422 struct in_addr group_addr
,
423 struct interface
*incoming
)
425 struct pim_upstream
*up
;
427 up
= pim_upstream_find(source_addr
, group_addr
);
432 up
= pim_upstream_new(source_addr
, group_addr
, incoming
);
438 void pim_upstream_del(struct pim_upstream
*up
)
442 if (up
->ref_count
< 1) {
443 pim_upstream_delete(up
);
448 Evaluate JoinDesired(S,G):
450 JoinDesired(S,G) is true if there is a downstream (S,G) interface I
453 inherited_olist(S,G) =
454 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
456 JoinDesired(S,G) may be affected by changes in the following:
458 pim_ifp->primary_address
460 ch->ifassert_winner_metric
462 ch->local_ifmembership
464 ch->upstream->rpf.source_nexthop.mrib_metric_preference
465 ch->upstream->rpf.source_nexthop.mrib_route_metric
466 ch->upstream->rpf.source_nexthop.interface
468 See also pim_upstream_update_join_desired() below.
470 int pim_upstream_evaluate_join_desired(struct pim_upstream
*up
)
472 struct listnode
*ifnode
;
473 struct listnode
*ifnextnode
;
474 struct listnode
*chnode
;
475 struct listnode
*chnextnode
;
476 struct interface
*ifp
;
477 struct pim_interface
*pim_ifp
;
478 struct pim_ifchannel
*ch
;
480 /* scan all interfaces */
481 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
486 /* scan per-interface (S,G) state */
487 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
488 if (ch
->upstream
!= up
)
491 if (pim_macro_ch_lost_assert(ch
))
492 continue; /* keep searching */
494 if (pim_macro_chisin_joins_or_include(ch
))
496 } /* scan iface channel list */
499 return 0; /* false */
503 See also pim_upstream_evaluate_join_desired() above.
505 void pim_upstream_update_join_desired(struct pim_upstream
*up
)
507 int was_join_desired
; /* boolean */
508 int is_join_desired
; /* boolean */
510 was_join_desired
= PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up
->flags
);
512 is_join_desired
= pim_upstream_evaluate_join_desired(up
);
514 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up
->flags
);
516 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up
->flags
);
518 /* switched from false to true */
519 if (is_join_desired
&& !was_join_desired
) {
520 zassert(up
->join_state
== PIM_UPSTREAM_NOTJOINED
);
521 pim_upstream_switch(up
, PIM_UPSTREAM_JOINED
);
525 /* switched from true to false */
526 if (!is_join_desired
&& was_join_desired
) {
527 zassert(up
->join_state
== PIM_UPSTREAM_JOINED
);
528 pim_upstream_switch(up
, PIM_UPSTREAM_NOTJOINED
);
534 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
535 Transitions from Joined State
536 RPF'(S,G) GenID changes
538 The upstream (S,G) state machine remains in Joined state. If the
539 Join Timer is set to expire in more than t_override seconds, reset
540 it so that it expires after t_override seconds.
542 void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr
)
544 struct listnode
*up_node
;
545 struct listnode
*up_nextnode
;
546 struct pim_upstream
*up
;
549 Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
551 for (ALL_LIST_ELEMENTS(qpim_upstream_list
, up_node
, up_nextnode
, up
)) {
553 if (PIM_DEBUG_PIM_TRACE
) {
557 char rpf_addr_str
[100];
558 pim_inet4_dump("<neigh?>", neigh_addr
, neigh_str
, sizeof(neigh_str
));
559 pim_inet4_dump("<src?>", up
->source_addr
, src_str
, sizeof(src_str
));
560 pim_inet4_dump("<grp?>", up
->group_addr
, grp_str
, sizeof(grp_str
));
561 pim_inet4_dump("<rpf?>", up
->rpf
.rpf_addr
, rpf_addr_str
, sizeof(rpf_addr_str
));
562 zlog_debug("%s: matching neigh=%s against upstream (S,G)=(%s,%s) joined=%d rpf_addr=%s",
564 neigh_str
, src_str
, grp_str
,
565 up
->join_state
== PIM_UPSTREAM_JOINED
,
569 /* consider only (S,G) upstream in Joined state */
570 if (up
->join_state
!= PIM_UPSTREAM_JOINED
)
573 /* match RPF'(S,G)=neigh_addr */
574 if (up
->rpf
.rpf_addr
.s_addr
!= neigh_addr
.s_addr
)
577 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
583 void pim_upstream_rpf_interface_changed(struct pim_upstream
*up
,
584 struct interface
*old_rpf_ifp
)
586 struct listnode
*ifnode
;
587 struct listnode
*ifnextnode
;
588 struct interface
*ifp
;
590 /* scan all interfaces */
591 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
592 struct listnode
*chnode
;
593 struct listnode
*chnextnode
;
594 struct pim_ifchannel
*ch
;
595 struct pim_interface
*pim_ifp
;
601 /* search all ifchannels */
602 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
603 if (ch
->upstream
!= up
)
606 if (ch
->ifassert_state
== PIM_IFASSERT_I_AM_LOSER
) {
608 /* RPF_interface(S) was NOT I */
609 (old_rpf_ifp
== ch
->interface
)
611 /* RPF_interface(S) stopped being I */
612 (ch
->upstream
->rpf
.source_nexthop
.interface
!= ch
->interface
)
614 assert_action_a5(ch
);
616 } /* PIM_IFASSERT_I_AM_LOSER */
618 pim_ifchannel_update_assert_tracking_desired(ch
);
623 void pim_upstream_update_could_assert(struct pim_upstream
*up
)
625 struct listnode
*ifnode
;
626 struct listnode
*ifnextnode
;
627 struct listnode
*chnode
;
628 struct listnode
*chnextnode
;
629 struct interface
*ifp
;
630 struct pim_interface
*pim_ifp
;
631 struct pim_ifchannel
*ch
;
633 /* scan all interfaces */
634 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
639 /* scan per-interface (S,G) state */
640 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
642 if (ch
->upstream
!= up
)
645 pim_ifchannel_update_could_assert(ch
);
647 } /* scan iface channel list */
651 void pim_upstream_update_my_assert_metric(struct pim_upstream
*up
)
653 struct listnode
*ifnode
;
654 struct listnode
*ifnextnode
;
655 struct listnode
*chnode
;
656 struct listnode
*chnextnode
;
657 struct interface
*ifp
;
658 struct pim_interface
*pim_ifp
;
659 struct pim_ifchannel
*ch
;
661 /* scan all interfaces */
662 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
667 /* scan per-interface (S,G) state */
668 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
670 if (ch
->upstream
!= up
)
673 pim_ifchannel_update_my_assert_metric(ch
);
675 } /* scan iface channel list */
679 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
)
681 struct listnode
*ifnode
;
682 struct listnode
*ifnextnode
;
683 struct listnode
*chnode
;
684 struct listnode
*chnextnode
;
685 struct interface
*ifp
;
686 struct pim_interface
*pim_ifp
;
687 struct pim_ifchannel
*ch
;
689 /* scan all interfaces */
690 for (ALL_LIST_ELEMENTS (vrf_iflist (VRF_DEFAULT
), ifnode
, ifnextnode
, ifp
)) {
695 /* scan per-interface (S,G) state */
696 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
698 if (ch
->upstream
!= up
)
701 pim_ifchannel_update_assert_tracking_desired(ch
);
703 } /* scan iface channel list */
708 * On an RP, the PMBR value must be cleared when the
709 * Keepalive Timer expires
712 pim_upstream_keep_alive_timer (struct thread
*t
)
714 struct pim_upstream
*up
;
718 if (I_am_RP (up
->group_addr
))
720 pim_br_clear_pmbr (up
->source_addr
, up
->group_addr
);
722 * We need to do more here :)
723 * But this is the start.
728 pim_mroute_update_counters (up
->channel_oil
);
730 if (up
->channel_oil
->cc
.oldpktcnt
>= up
->channel_oil
->cc
.pktcnt
)
732 pim_mroute_del (up
->channel_oil
);
733 pim_upstream_delete (up
);
737 up
->t_ka_timer
= NULL
;
738 pim_upstream_keep_alive_timer_start (up
, PIM_KEEPALIVE_PERIOD
);
745 pim_upstream_keep_alive_timer_start (struct pim_upstream
*up
,
748 THREAD_TIMER_ON (master
,
750 pim_upstream_keep_alive_timer
,
755 * 4.2.1 Last-Hop Switchover to the SPT
757 * In Sparse-Mode PIM, last-hop routers join the shared tree towards the
758 * RP. Once traffic from sources to joined groups arrives at a last-hop
759 * router, it has the option of switching to receive the traffic on a
760 * shortest path tree (SPT).
762 * The decision for a router to switch to the SPT is controlled as
766 * CheckSwitchToSpt(S,G) {
767 * if ( ( pim_include(*,G) (-) pim_exclude(S,G)
768 * (+) pim_include(S,G) != NULL )
769 * AND SwitchToSptDesired(S,G) ) {
770 * # Note: Restarting the KAT will result in the SPT switch
771 * set KeepaliveTimer(S,G) to Keepalive_Period
775 * SwitchToSptDesired(S,G) is a policy function that is implementation
776 * defined. An "infinite threshold" policy can be implemented by making
777 * SwitchToSptDesired(S,G) return false all the time. A "switch on
778 * first packet" policy can be implemented by making
779 * SwitchToSptDesired(S,G) return true once a single packet has been
780 * received for the source and group.
783 pim_upstream_switch_to_spt_desired (struct in_addr source
, struct in_addr group
)