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"
40 #include "pim_iface.h"
42 #include "pim_zlookup.h"
43 #include "pim_upstream.h"
44 #include "pim_ifchannel.h"
45 #include "pim_neighbor.h"
47 #include "pim_zebra.h"
49 #include "pim_macro.h"
52 #include "pim_register.h"
55 struct hash
*pim_upstream_hash
= NULL
;
56 struct list
*pim_upstream_list
= NULL
;
57 struct timer_wheel
*pim_upstream_sg_wheel
= NULL
;
59 static void join_timer_start(struct pim_upstream
*up
);
60 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
);
63 * A (*,G) or a (*,*) is going away
64 * remove the parent pointer from
65 * those pointing at us
68 pim_upstream_remove_children (struct pim_upstream
*up
)
70 struct pim_upstream
*child
;
75 while (!list_isempty (up
->sources
))
77 child
= listnode_head (up
->sources
);
79 listnode_delete (up
->sources
, child
);
84 * A (*,G) or a (*,*) is being created
85 * Find the children that would point
89 pim_upstream_find_new_children (struct pim_upstream
*up
)
91 struct pim_upstream
*child
;
92 struct listnode
*ch_node
;
94 if ((up
->sg
.src
.s_addr
!= INADDR_ANY
) &&
95 (up
->sg
.grp
.s_addr
!= INADDR_ANY
))
98 if ((up
->sg
.src
.s_addr
== INADDR_ANY
) &&
99 (up
->sg
.grp
.s_addr
== INADDR_ANY
))
102 for (ALL_LIST_ELEMENTS_RO (pim_upstream_list
, ch_node
, child
))
104 if ((up
->sg
.grp
.s_addr
!= INADDR_ANY
) &&
105 (child
->sg
.grp
.s_addr
== up
->sg
.grp
.s_addr
) &&
109 listnode_add_sort (up
->sources
, child
);
115 * If we have a (*,*) || (S,*) there is no parent
116 * If we have a (S,G), find the (*,G)
117 * If we have a (*,G), find the (*,*)
119 static struct pim_upstream
*
120 pim_upstream_find_parent (struct pim_upstream
*child
)
122 struct prefix_sg any
= child
->sg
;
123 struct pim_upstream
*up
= NULL
;
126 if ((child
->sg
.src
.s_addr
!= INADDR_ANY
) &&
127 (child
->sg
.grp
.s_addr
!= INADDR_ANY
))
129 any
.src
.s_addr
= INADDR_ANY
;
130 up
= pim_upstream_find (&any
);
133 listnode_add (up
->sources
, child
);
141 void pim_upstream_free(struct pim_upstream
*up
)
143 XFREE(MTYPE_PIM_UPSTREAM
, up
);
146 static void upstream_channel_oil_detach(struct pim_upstream
*up
)
148 if (up
->channel_oil
) {
149 pim_channel_oil_del(up
->channel_oil
);
150 up
->channel_oil
= NULL
;
155 pim_upstream_del(struct pim_upstream
*up
, const char *name
)
157 bool notify_msdp
= false;
160 zlog_debug ("%s(%s): Delete %s ref count: %d",
161 __PRETTY_FUNCTION__
, name
, up
->sg_str
, up
->ref_count
);
165 if (up
->ref_count
>= 1)
168 THREAD_OFF(up
->t_join_timer
);
169 THREAD_OFF(up
->t_ka_timer
);
170 THREAD_OFF(up
->t_rs_timer
);
171 THREAD_OFF(up
->t_msdp_reg_timer
);
173 if (up
->join_state
== PIM_UPSTREAM_JOINED
) {
174 pim_joinprune_send (&up
->rpf
, up
, 0);
175 if (up
->sg
.src
.s_addr
== INADDR_ANY
) {
176 /* if a (*, G) entry in the joined state is being deleted we
177 * need to notify MSDP */
182 if (up
->sg
.src
.s_addr
!= INADDR_ANY
) {
183 wheel_remove_item (pim_upstream_sg_wheel
, up
);
187 pim_upstream_remove_children (up
);
188 pim_mroute_del (up
->channel_oil
, __PRETTY_FUNCTION__
);
189 upstream_channel_oil_detach(up
);
192 list_delete (up
->sources
);
196 notice that listnode_delete() can't be moved
197 into pim_upstream_free() because the later is
198 called by list_delete_all_node()
202 listnode_delete (up
->parent
->sources
, up
);
205 listnode_delete (pim_upstream_list
, up
);
206 hash_release (pim_upstream_hash
, up
);
209 pim_msdp_up_del(&up
->sg
);
211 pim_upstream_free(up
);
215 pim_upstream_send_join (struct pim_upstream
*up
)
217 if (PIM_DEBUG_TRACE
) {
218 char rpf_str
[PREFIX_STRLEN
];
219 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_str
, sizeof(rpf_str
));
220 zlog_debug ("%s: RPF'%s=%s(%s) for Interface %s", __PRETTY_FUNCTION__
,
221 up
->sg_str
, rpf_str
, pim_upstream_state2str (up
->join_state
),
222 up
->rpf
.source_nexthop
.interface
->name
);
223 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
)) {
224 zlog_debug("%s: can't send join upstream: RPF'%s=%s",
226 up
->sg_str
, rpf_str
);
231 /* send Join(S,G) to the current upstream neighbor */
232 pim_joinprune_send(&up
->rpf
, up
, 1 /* join */);
235 static int on_join_timer(struct thread
*t
)
237 struct pim_upstream
*up
;
241 up
->t_join_timer
= NULL
;
244 * In the case of a HFR we will not ahve anyone to send this to.
246 if (PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
250 * Don't send the join if the outgoing interface is a loopback
251 * But since this might change leave the join timer running
253 if (!if_is_loopback (up
->rpf
.source_nexthop
.interface
))
254 pim_upstream_send_join (up
);
256 join_timer_start(up
);
261 static void join_timer_start(struct pim_upstream
*up
)
263 if (PIM_DEBUG_PIM_EVENTS
) {
264 zlog_debug("%s: starting %d sec timer for upstream (S,G)=%s",
270 THREAD_OFF (up
->t_join_timer
);
271 THREAD_TIMER_ON(master
, up
->t_join_timer
,
273 up
, qpim_t_periodic
);
276 void pim_upstream_join_timer_restart(struct pim_upstream
*up
)
278 THREAD_OFF(up
->t_join_timer
);
279 join_timer_start(up
);
282 static void pim_upstream_join_timer_restart_msec(struct pim_upstream
*up
,
285 if (PIM_DEBUG_PIM_EVENTS
) {
286 zlog_debug("%s: restarting %d msec timer for upstream (S,G)=%s",
292 THREAD_OFF(up
->t_join_timer
);
293 THREAD_TIMER_MSEC_ON(master
, up
->t_join_timer
,
298 void pim_upstream_join_suppress(struct pim_upstream
*up
,
299 struct in_addr rpf_addr
,
302 long t_joinsuppress_msec
;
303 long join_timer_remain_msec
;
305 t_joinsuppress_msec
= MIN(pim_if_t_suppressed_msec(up
->rpf
.source_nexthop
.interface
),
308 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
310 if (PIM_DEBUG_TRACE
) {
311 char rpf_str
[INET_ADDRSTRLEN
];
312 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
313 zlog_debug("%s %s: detected Join%s to RPF'(S,G)=%s: join_timer=%ld msec t_joinsuppress=%ld msec",
314 __FILE__
, __PRETTY_FUNCTION__
,
317 join_timer_remain_msec
, t_joinsuppress_msec
);
320 if (join_timer_remain_msec
< t_joinsuppress_msec
) {
321 if (PIM_DEBUG_TRACE
) {
322 zlog_debug("%s %s: suppressing Join(S,G)=%s for %ld msec",
323 __FILE__
, __PRETTY_FUNCTION__
,
324 up
->sg_str
, t_joinsuppress_msec
);
327 pim_upstream_join_timer_restart_msec(up
, t_joinsuppress_msec
);
331 void pim_upstream_join_timer_decrease_to_t_override(const char *debug_label
,
332 struct pim_upstream
*up
)
334 long join_timer_remain_msec
;
337 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
338 t_override_msec
= pim_if_t_override_msec(up
->rpf
.source_nexthop
.interface
);
340 if (PIM_DEBUG_TRACE
) {
341 char rpf_str
[INET_ADDRSTRLEN
];
342 pim_inet4_dump("<rpf?>", up
->rpf
.rpf_addr
.u
.prefix4
, rpf_str
, sizeof(rpf_str
));
343 zlog_debug("%s: to RPF'%s=%s: join_timer=%ld msec t_override=%d msec",
346 join_timer_remain_msec
, t_override_msec
);
349 if (join_timer_remain_msec
> t_override_msec
) {
350 if (PIM_DEBUG_TRACE
) {
351 zlog_debug("%s: decreasing (S,G)=%s join timer to t_override=%d msec",
357 pim_upstream_join_timer_restart_msec(up
, t_override_msec
);
361 static void forward_on(struct pim_upstream
*up
)
363 struct listnode
*chnode
;
364 struct listnode
*chnextnode
;
365 struct pim_interface
*pim_ifp
;
366 struct pim_ifchannel
*ch
;
368 /* scan (S,G) state */
369 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
370 pim_ifp
= ch
->interface
->info
;
374 if (ch
->upstream
!= up
)
377 if (pim_macro_chisin_oiflist(ch
))
378 pim_forward_start(ch
);
380 } /* scan iface channel list */
383 static void forward_off(struct pim_upstream
*up
)
385 struct listnode
*chnode
;
386 struct listnode
*chnextnode
;
387 struct pim_interface
*pim_ifp
;
388 struct pim_ifchannel
*ch
;
390 /* scan per-interface (S,G) state */
391 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
392 pim_ifp
= ch
->interface
->info
;
396 if (ch
->upstream
!= up
)
399 pim_forward_stop(ch
);
401 } /* scan iface channel list */
405 pim_upstream_could_register (struct pim_upstream
*up
)
407 struct pim_interface
*pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
409 if (pim_ifp
&& PIM_I_am_DR (pim_ifp
) &&
410 pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
417 pim_upstream_switch(struct pim_upstream
*up
,
418 enum pim_upstream_state new_state
)
420 enum pim_upstream_state old_state
= up
->join_state
;
422 if (PIM_DEBUG_PIM_EVENTS
) {
423 zlog_debug("%s: PIM_UPSTREAM_%s: (S,G) old: %s new: %s",
426 pim_upstream_state2str (up
->join_state
),
427 pim_upstream_state2str (new_state
));
431 * This code still needs work.
433 switch (up
->join_state
)
435 case PIM_UPSTREAM_PRUNE
:
436 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
438 up
->join_state
= new_state
;
439 up
->state_transition
= pim_time_monotonic_sec ();
442 case PIM_UPSTREAM_JOIN_PENDING
:
444 case PIM_UPSTREAM_NOTJOINED
:
445 case PIM_UPSTREAM_JOINED
:
446 up
->join_state
= new_state
;
447 if (old_state
!= new_state
)
448 up
->state_transition
= pim_time_monotonic_sec();
453 pim_upstream_update_assert_tracking_desired(up
);
455 if (new_state
== PIM_UPSTREAM_JOINED
) {
456 if (old_state
!= PIM_UPSTREAM_JOINED
)
458 int old_fhr
= PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
);
460 pim_msdp_up_join_state_changed(up
);
461 if (pim_upstream_could_register (up
))
463 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
464 if (!old_fhr
&& PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
466 pim_upstream_keep_alive_timer_start (up
, qpim_keep_alive_time
);
467 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
472 pim_upstream_send_join (up
);
473 join_timer_start (up
);
483 if (old_state
== PIM_UPSTREAM_JOINED
)
484 pim_msdp_up_join_state_changed(up
);
485 pim_joinprune_send(&up
->rpf
, up
, 0 /* prune */);
486 if (up
->t_join_timer
)
487 THREAD_OFF(up
->t_join_timer
);
492 pim_upstream_compare (void *arg1
, void *arg2
)
494 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
495 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
497 if (ntohl(up1
->sg
.grp
.s_addr
) < ntohl(up2
->sg
.grp
.s_addr
))
500 if (ntohl(up1
->sg
.grp
.s_addr
) > ntohl(up2
->sg
.grp
.s_addr
))
503 if (ntohl(up1
->sg
.src
.s_addr
) < ntohl(up2
->sg
.src
.s_addr
))
506 if (ntohl(up1
->sg
.src
.s_addr
) > ntohl(up2
->sg
.src
.s_addr
))
512 static struct pim_upstream
*
513 pim_upstream_new (struct prefix_sg
*sg
,
514 struct interface
*incoming
,
517 enum pim_rpf_result rpf_result
;
518 struct pim_interface
*pim_ifp
;
519 struct pim_upstream
*up
;
521 up
= XCALLOC(MTYPE_PIM_UPSTREAM
, sizeof(*up
));
523 zlog_err("%s: PIM XCALLOC(%zu) failure",
524 __PRETTY_FUNCTION__
, sizeof(*up
));
529 pim_str_sg_set (sg
, up
->sg_str
);
530 up
= hash_get (pim_upstream_hash
, up
, hash_alloc_intern
);
531 if (!pim_rp_set_upstream_addr (&up
->upstream_addr
, sg
->src
, sg
->grp
))
534 zlog_debug("%s: Received a (*,G) with no RP configured", __PRETTY_FUNCTION__
);
536 hash_release (pim_upstream_hash
, up
);
537 XFREE (MTYPE_PIM_UPSTREAM
, up
);
541 up
->parent
= pim_upstream_find_parent (up
);
542 if (up
->sg
.src
.s_addr
== INADDR_ANY
)
544 up
->sources
= list_new ();
545 up
->sources
->cmp
= pim_upstream_compare
;
550 pim_upstream_find_new_children (up
);
553 up
->t_join_timer
= NULL
;
554 up
->t_ka_timer
= NULL
;
555 up
->t_rs_timer
= NULL
;
556 up
->t_msdp_reg_timer
= NULL
;
558 up
->state_transition
= pim_time_monotonic_sec();
559 up
->channel_oil
= NULL
;
560 up
->sptbit
= PIM_UPSTREAM_SPTBIT_FALSE
;
562 up
->rpf
.source_nexthop
.interface
= NULL
;
563 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.family
= AF_INET
;
564 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
565 up
->rpf
.source_nexthop
.mrib_metric_preference
= qpim_infinite_assert_metric
.metric_preference
;
566 up
->rpf
.source_nexthop
.mrib_route_metric
= qpim_infinite_assert_metric
.route_metric
;
567 up
->rpf
.rpf_addr
.family
= AF_INET
;
568 up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
570 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
571 wheel_add_item (pim_upstream_sg_wheel
, up
);
573 rpf_result
= pim_rpf_update(up
, NULL
);
574 if (rpf_result
== PIM_RPF_FAILURE
) {
576 zlog_debug ("%s: Attempting to create upstream(%s), Unable to RPF for source", __PRETTY_FUNCTION__
,
581 listnode_delete (up
->parent
->sources
, up
);
585 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
586 wheel_remove_item (pim_upstream_sg_wheel
, up
);
588 pim_upstream_remove_children (up
);
590 list_delete (up
->sources
);
592 hash_release (pim_upstream_hash
, up
);
593 XFREE(MTYPE_PIM_UPSTREAM
, up
);
597 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
599 up
->channel_oil
= pim_channel_oil_add(&up
->sg
, pim_ifp
->mroute_vif_index
);
601 listnode_add_sort(pim_upstream_list
, up
);
604 zlog_debug ("%s: Created Upstream %s", __PRETTY_FUNCTION__
, up
->sg_str
);
609 struct pim_upstream
*pim_upstream_find(struct prefix_sg
*sg
)
611 struct pim_upstream lookup
;
612 struct pim_upstream
*up
= NULL
;
615 up
= hash_lookup (pim_upstream_hash
, &lookup
);
619 static void pim_upstream_ref(struct pim_upstream
*up
, int flags
)
625 struct pim_upstream
*pim_upstream_add(struct prefix_sg
*sg
,
626 struct interface
*incoming
,
627 int flags
, const char *name
)
629 struct pim_upstream
*up
= NULL
;
631 up
= pim_upstream_find(sg
);
633 pim_upstream_ref(up
, flags
);
637 up
= pim_upstream_new(sg
, incoming
, flags
);
643 zlog_debug("%s(%s): %s, found: %d: ref_count: %d",
644 __PRETTY_FUNCTION__
, name
,
648 zlog_debug("%s(%s): (%s) failure to create",
649 __PRETTY_FUNCTION__
, name
,
650 pim_str_sg_dump (sg
));
657 pim_upstream_evaluate_join_desired_interface (struct pim_upstream
*up
,
658 struct pim_ifchannel
*ch
)
660 struct pim_upstream
*parent
= up
->parent
;
662 if (ch
->upstream
== up
)
664 if (!pim_macro_ch_lost_assert(ch
) && pim_macro_chisin_joins_or_include(ch
))
667 if (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
))
674 if (parent
&& ch
->upstream
== parent
)
676 if (!pim_macro_ch_lost_assert (ch
) && pim_macro_chisin_joins_or_include (ch
))
684 Evaluate JoinDesired(S,G):
686 JoinDesired(S,G) is true if there is a downstream (S,G) interface I
689 inherited_olist(S,G) =
690 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
692 JoinDesired(S,G) may be affected by changes in the following:
694 pim_ifp->primary_address
696 ch->ifassert_winner_metric
698 ch->local_ifmembership
700 ch->upstream->rpf.source_nexthop.mrib_metric_preference
701 ch->upstream->rpf.source_nexthop.mrib_route_metric
702 ch->upstream->rpf.source_nexthop.interface
704 See also pim_upstream_update_join_desired() below.
706 int pim_upstream_evaluate_join_desired(struct pim_upstream
*up
)
708 struct listnode
*chnode
;
709 struct listnode
*chnextnode
;
710 struct pim_interface
*pim_ifp
;
711 struct pim_ifchannel
*ch
;
714 /* scan per-interface (S,G) state */
715 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
))
717 pim_ifp
= ch
->interface
->info
;
721 ret
+= pim_upstream_evaluate_join_desired_interface (up
, ch
);
722 } /* scan iface channel list */
724 return ret
; /* false */
728 See also pim_upstream_evaluate_join_desired() above.
730 void pim_upstream_update_join_desired(struct pim_upstream
*up
)
732 int was_join_desired
; /* boolean */
733 int is_join_desired
; /* boolean */
735 was_join_desired
= PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up
->flags
);
737 is_join_desired
= pim_upstream_evaluate_join_desired(up
);
739 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up
->flags
);
741 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up
->flags
);
743 /* switched from false to true */
744 if (is_join_desired
&& !was_join_desired
) {
745 pim_upstream_switch(up
, PIM_UPSTREAM_JOINED
);
749 /* switched from true to false */
750 if (!is_join_desired
&& was_join_desired
) {
751 pim_upstream_switch(up
, PIM_UPSTREAM_NOTJOINED
);
757 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
758 Transitions from Joined State
759 RPF'(S,G) GenID changes
761 The upstream (S,G) state machine remains in Joined state. If the
762 Join Timer is set to expire in more than t_override seconds, reset
763 it so that it expires after t_override seconds.
765 void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr
)
767 struct listnode
*up_node
;
768 struct listnode
*up_nextnode
;
769 struct pim_upstream
*up
;
772 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
774 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
)) {
776 if (PIM_DEBUG_TRACE
) {
777 char neigh_str
[INET_ADDRSTRLEN
];
778 char rpf_addr_str
[PREFIX_STRLEN
];
779 pim_inet4_dump("<neigh?>", neigh_addr
, neigh_str
, sizeof(neigh_str
));
780 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_addr_str
, sizeof(rpf_addr_str
));
781 zlog_debug("%s: matching neigh=%s against upstream (S,G)=%s joined=%d rpf_addr=%s",
783 neigh_str
, up
->sg_str
,
784 up
->join_state
== PIM_UPSTREAM_JOINED
,
788 /* consider only (S,G) upstream in Joined state */
789 if (up
->join_state
!= PIM_UPSTREAM_JOINED
)
792 /* match RPF'(S,G)=neigh_addr */
793 if (up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
!= neigh_addr
.s_addr
)
796 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
802 void pim_upstream_rpf_interface_changed(struct pim_upstream
*up
,
803 struct interface
*old_rpf_ifp
)
805 struct listnode
*chnode
;
806 struct listnode
*chnextnode
;
807 struct pim_ifchannel
*ch
;
808 struct pim_interface
*pim_ifp
;
810 /* search all ifchannels */
811 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
813 pim_ifp
= ch
->interface
->info
;
817 if (ch
->upstream
!= up
)
820 if (ch
->ifassert_state
== PIM_IFASSERT_I_AM_LOSER
) {
822 /* RPF_interface(S) was NOT I */
823 (old_rpf_ifp
== ch
->interface
)
825 /* RPF_interface(S) stopped being I */
826 (ch
->upstream
->rpf
.source_nexthop
.interface
!= ch
->interface
)
828 assert_action_a5(ch
);
830 } /* PIM_IFASSERT_I_AM_LOSER */
832 pim_ifchannel_update_assert_tracking_desired(ch
);
836 void pim_upstream_update_could_assert(struct pim_upstream
*up
)
838 struct listnode
*chnode
;
839 struct listnode
*chnextnode
;
840 struct pim_interface
*pim_ifp
;
841 struct pim_ifchannel
*ch
;
843 /* scan per-interface (S,G) state */
844 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
845 pim_ifp
= ch
->interface
->info
;
849 if (ch
->upstream
!= up
)
852 pim_ifchannel_update_could_assert(ch
);
853 } /* scan iface channel list */
856 void pim_upstream_update_my_assert_metric(struct pim_upstream
*up
)
858 struct listnode
*chnode
;
859 struct listnode
*chnextnode
;
860 struct pim_interface
*pim_ifp
;
861 struct pim_ifchannel
*ch
;
863 /* scan per-interface (S,G) state */
864 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
865 pim_ifp
= ch
->interface
->info
;
869 if (ch
->upstream
!= up
)
872 pim_ifchannel_update_my_assert_metric(ch
);
874 } /* scan iface channel list */
877 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
)
879 struct listnode
*chnode
;
880 struct listnode
*chnextnode
;
881 struct pim_interface
*pim_ifp
;
882 struct pim_ifchannel
*ch
;
884 /* scan per-interface (S,G) state */
885 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
886 pim_ifp
= ch
->interface
->info
;
890 if (ch
->upstream
!= up
)
893 pim_ifchannel_update_assert_tracking_desired(ch
);
895 } /* scan iface channel list */
898 /* When kat is stopped CouldRegister goes to false so we need to
899 * transition the (S, G) on FHR to NI state and remove reg tunnel
901 static void pim_upstream_fhr_kat_expiry(struct pim_upstream
*up
)
903 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
907 zlog_debug ("kat expired on %s; clear fhr reg state", up
->sg_str
);
909 /* stop reg-stop timer */
910 THREAD_OFF(up
->t_rs_timer
);
911 /* remove regiface from the OIL if it is there*/
912 pim_channel_del_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
913 /* move to "not-joined" */
914 up
->join_state
= PIM_UPSTREAM_NOTJOINED
;
915 PIM_UPSTREAM_FLAG_UNSET_FHR(up
->flags
);
918 /* When kat is started CouldRegister can go to true. And if it does we
919 * need to transition the (S, G) on FHR to JOINED state and add reg tunnel
921 static void pim_upstream_fhr_kat_start(struct pim_upstream
*up
)
923 if (pim_upstream_could_register(up
)) {
925 zlog_debug ("kat started on %s; set fhr reg state to joined", up
->sg_str
);
927 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
928 if (up
->join_state
== PIM_UPSTREAM_NOTJOINED
) {
929 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
930 up
->join_state
= PIM_UPSTREAM_JOINED
;
936 * On an RP, the PMBR value must be cleared when the
937 * Keepalive Timer expires
938 * KAT expiry indicates that flow is inactive. If the flow was created or
939 * maintained by activity now is the time to deref it.
942 pim_upstream_keep_alive_timer (struct thread
*t
)
944 struct pim_upstream
*up
;
947 up
->t_ka_timer
= NULL
;
949 if (I_am_RP (up
->sg
.grp
))
951 pim_br_clear_pmbr (&up
->sg
);
953 * We need to do more here :)
954 * But this is the start.
958 /* source is no longer active - pull the SA from MSDP's cache */
959 pim_msdp_sa_local_del(&up
->sg
);
961 /* if entry was created because of activity we need to deref it */
962 if (PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
964 pim_upstream_fhr_kat_expiry(up
);
966 zlog_debug ("kat expired on %s; remove stream reference", up
->sg_str
);
967 PIM_UPSTREAM_FLAG_UNSET_SRC_STREAM(up
->flags
);
968 pim_upstream_del(up
, __PRETTY_FUNCTION__
);
975 pim_upstream_keep_alive_timer_start (struct pim_upstream
*up
,
978 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
)) {
980 zlog_debug ("kat start on %s with no stream reference", up
->sg_str
);
982 THREAD_OFF (up
->t_ka_timer
);
983 THREAD_TIMER_ON (master
,
985 pim_upstream_keep_alive_timer
,
988 /* any time keepalive is started against a SG we will have to
989 * re-evaluate our active source database */
990 pim_msdp_sa_local_update(up
);
993 /* MSDP on RP needs to know if a source is registerable to this RP */
995 pim_upstream_msdp_reg_timer(struct thread
*t
)
997 struct pim_upstream
*up
;
1000 up
->t_msdp_reg_timer
= NULL
;
1002 /* source is no longer active - pull the SA from MSDP's cache */
1003 pim_msdp_sa_local_del(&up
->sg
);
1007 pim_upstream_msdp_reg_timer_start(struct pim_upstream
*up
)
1009 THREAD_OFF(up
->t_msdp_reg_timer
);
1010 THREAD_TIMER_ON(master
, up
->t_msdp_reg_timer
,
1011 pim_upstream_msdp_reg_timer
, up
, PIM_MSDP_REG_RXED_PERIOD
);
1013 pim_msdp_sa_local_update(up
);
1017 * 4.2.1 Last-Hop Switchover to the SPT
1019 * In Sparse-Mode PIM, last-hop routers join the shared tree towards the
1020 * RP. Once traffic from sources to joined groups arrives at a last-hop
1021 * router, it has the option of switching to receive the traffic on a
1022 * shortest path tree (SPT).
1024 * The decision for a router to switch to the SPT is controlled as
1028 * CheckSwitchToSpt(S,G) {
1029 * if ( ( pim_include(*,G) (-) pim_exclude(S,G)
1030 * (+) pim_include(S,G) != NULL )
1031 * AND SwitchToSptDesired(S,G) ) {
1032 * # Note: Restarting the KAT will result in the SPT switch
1033 * set KeepaliveTimer(S,G) to Keepalive_Period
1037 * SwitchToSptDesired(S,G) is a policy function that is implementation
1038 * defined. An "infinite threshold" policy can be implemented by making
1039 * SwitchToSptDesired(S,G) return false all the time. A "switch on
1040 * first packet" policy can be implemented by making
1041 * SwitchToSptDesired(S,G) return true once a single packet has been
1042 * received for the source and group.
1045 pim_upstream_switch_to_spt_desired (struct prefix_sg
*sg
)
1047 if (I_am_RP (sg
->grp
))
1054 pim_upstream_is_sg_rpt (struct pim_upstream
*up
)
1056 struct listnode
*chnode
;
1057 struct pim_ifchannel
*ch
;
1059 for (ALL_LIST_ELEMENTS_RO(pim_ifchannel_list
, chnode
, ch
))
1061 if ((ch
->upstream
== up
) &&
1062 (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
)))
1069 * After receiving a packet set SPTbit:
1071 * Update_SPTbit(S,G,iif) {
1072 * if ( iif == RPF_interface(S)
1073 * AND JoinDesired(S,G) == TRUE
1074 * AND ( DirectlyConnected(S) == TRUE
1075 * OR RPF_interface(S) != RPF_interface(RP(G))
1076 * OR inherited_olist(S,G,rpt) == NULL
1077 * OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1078 * ( RPF'(S,G) != NULL ) )
1079 * OR ( I_Am_Assert_Loser(S,G,iif) ) {
1080 * Set SPTbit(S,G) to TRUE
1085 pim_upstream_set_sptbit (struct pim_upstream
*up
, struct interface
*incoming
)
1087 struct pim_rpf
*grpf
= NULL
;
1089 // iif == RPF_interfvace(S)
1090 if (up
->rpf
.source_nexthop
.interface
!= incoming
)
1092 if (PIM_DEBUG_TRACE
)
1093 zlog_debug ("%s: Incoming Interface: %s is different than RPF_interface(S) %s",
1094 __PRETTY_FUNCTION__
, incoming
->name
, up
->rpf
.source_nexthop
.interface
->name
);
1098 // AND JoinDesired(S,G) == TRUE
1101 // DirectlyConnected(S) == TRUE
1102 if (pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
1104 if (PIM_DEBUG_TRACE
)
1105 zlog_debug ("%s: %s is directly connected to the source", __PRETTY_FUNCTION__
,
1107 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1111 // OR RPF_interface(S) != RPF_interface(RP(G))
1112 grpf
= RP(up
->sg
.grp
);
1113 if (!grpf
|| up
->rpf
.source_nexthop
.interface
!= grpf
->source_nexthop
.interface
)
1115 if (PIM_DEBUG_TRACE
)
1116 zlog_debug ("%s: %s RPF_interface(S) != RPF_interface(RP(G))",
1117 __PRETTY_FUNCTION__
, up
->sg_str
);
1118 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1122 // OR inherited_olist(S,G,rpt) == NULL
1123 if (pim_upstream_is_sg_rpt(up
) && pim_upstream_empty_inherited_olist(up
))
1125 if (PIM_DEBUG_TRACE
)
1126 zlog_debug ("%s: %s OR inherited_olist(S,G,rpt) == NULL", __PRETTY_FUNCTION__
,
1128 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1132 // OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1133 // ( RPF'(S,G) != NULL ) )
1134 if (up
->parent
&& pim_rpf_is_same (&up
->rpf
, &up
->parent
->rpf
))
1136 if (PIM_DEBUG_TRACE
)
1137 zlog_debug ("%s: %s RPF'(S,G) is the same as RPF'(*,G)", __PRETTY_FUNCTION__
,
1139 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1147 pim_upstream_state2str (enum pim_upstream_state join_state
)
1151 case PIM_UPSTREAM_NOTJOINED
:
1154 case PIM_UPSTREAM_JOINED
:
1157 case PIM_UPSTREAM_JOIN_PENDING
:
1158 return "JoinPending";
1160 case PIM_UPSTREAM_PRUNE
:
1168 pim_upstream_register_stop_timer (struct thread
*t
)
1170 struct pim_interface
*pim_ifp
;
1171 struct pim_upstream
*up
;
1172 struct pim_rpf
*rpg
;
1174 up
= THREAD_ARG (t
);
1176 up
->t_rs_timer
= NULL
;
1178 if (PIM_DEBUG_TRACE
)
1180 zlog_debug ("%s: (S,G)=%s upstream register stop timer %s",
1181 __PRETTY_FUNCTION__
, up
->sg_str
,
1182 pim_upstream_state2str(up
->join_state
));
1185 switch (up
->join_state
)
1187 case PIM_UPSTREAM_JOIN_PENDING
:
1188 up
->join_state
= PIM_UPSTREAM_JOINED
;
1189 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
1191 case PIM_UPSTREAM_JOINED
:
1193 case PIM_UPSTREAM_PRUNE
:
1194 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1197 if (PIM_DEBUG_TRACE
)
1198 zlog_debug ("%s: Interface: %s is not configured for pim",
1199 __PRETTY_FUNCTION__
, up
->rpf
.source_nexthop
.interface
->name
);
1202 up
->join_state
= PIM_UPSTREAM_JOIN_PENDING
;
1203 pim_upstream_start_register_stop_timer (up
, 1);
1205 if (((up
->channel_oil
->cc
.lastused
/100) > PIM_KEEPALIVE_PERIOD
) &&
1206 (I_am_RP (up
->sg
.grp
)))
1208 if (PIM_DEBUG_TRACE
)
1209 zlog_debug ("%s: Stop sending the register, because I am the RP and we haven't seen a packet in a while", __PRETTY_FUNCTION__
);
1212 rpg
= RP (up
->sg
.grp
);
1213 memset (&ip_hdr
, 0, sizeof (struct ip
));
1214 ip_hdr
.ip_p
= PIM_IP_PROTO_PIM
;
1217 ip_hdr
.ip_src
= up
->sg
.src
;
1218 ip_hdr
.ip_dst
= up
->sg
.grp
;
1219 ip_hdr
.ip_len
= htons (20);
1220 // checksum is broken
1221 pim_register_send ((uint8_t *)&ip_hdr
, sizeof (struct ip
),
1222 pim_ifp
->primary_address
, rpg
, 1, up
);
1232 pim_upstream_start_register_stop_timer (struct pim_upstream
*up
, int null_register
)
1238 THREAD_TIMER_OFF (up
->t_rs_timer
);
1239 up
->t_rs_timer
= NULL
;
1244 uint32_t lower
= (0.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1245 uint32_t upper
= (1.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1246 time
= lower
+ (random () % (upper
- lower
+ 1)) - PIM_REGISTER_PROBE_PERIOD
;
1249 time
= PIM_REGISTER_PROBE_PERIOD
;
1251 if (PIM_DEBUG_TRACE
)
1253 zlog_debug ("%s: (S,G)=%s Starting upstream register stop timer %d",
1254 __PRETTY_FUNCTION__
, up
->sg_str
, time
);
1256 THREAD_TIMER_ON (master
, up
->t_rs_timer
,
1257 pim_upstream_register_stop_timer
,
1262 pim_upstream_inherited_olist_decide (struct pim_upstream
*up
)
1264 struct pim_interface
*pim_ifp
;
1265 struct listnode
*chnextnode
;
1266 struct pim_ifchannel
*ch
;
1267 struct listnode
*chnode
;
1268 int output_intf
= 0;
1270 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1271 if (pim_ifp
&& !up
->channel_oil
)
1272 up
->channel_oil
= pim_channel_oil_add (&up
->sg
, pim_ifp
->mroute_vif_index
);
1274 for (ALL_LIST_ELEMENTS (pim_ifchannel_list
, chnode
, chnextnode
, ch
))
1276 pim_ifp
= ch
->interface
->info
;
1280 if (pim_upstream_evaluate_join_desired_interface (up
, ch
))
1282 int flag
= PIM_OIF_FLAG_PROTO_PIM
;
1284 if (ch
->sg
.src
.s_addr
== INADDR_ANY
&& ch
->upstream
!= up
)
1285 flag
= PIM_OIF_FLAG_PROTO_STAR
;
1286 pim_channel_add_oif (up
->channel_oil
, ch
->interface
, flag
);
1295 * For a given upstream, determine the inherited_olist
1298 * inherited_olist(S,G,rpt) =
1299 * ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
1300 * (+) ( pim_include(*,G) (-) pim_exclude(S,G))
1301 * (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) )
1303 * inherited_olist(S,G) =
1304 * inherited_olist(S,G,rpt) (+)
1305 * joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
1307 * return 1 if there are any output interfaces
1308 * return 0 if there are not any output interfaces
1311 pim_upstream_inherited_olist (struct pim_upstream
*up
)
1313 int output_intf
= pim_upstream_inherited_olist_decide (up
);
1316 * If we have output_intf switch state to Join and work like normal
1317 * If we don't have an output_intf that means we are probably a
1318 * switch on a stick so turn on forwarding to just accept the
1319 * incoming packets so we don't bother the other stuff!
1322 pim_upstream_switch (up
, PIM_UPSTREAM_JOINED
);
1330 pim_upstream_empty_inherited_olist (struct pim_upstream
*up
)
1332 return pim_channel_oil_empty (up
->channel_oil
);
1336 * When we have a new neighbor,
1337 * find upstreams that don't have their rpf_addr
1338 * set and see if the new neighbor allows
1339 * the join to be sent
1342 pim_upstream_find_new_rpf (void)
1344 struct listnode
*up_node
;
1345 struct listnode
*up_nextnode
;
1346 struct pim_upstream
*up
;
1349 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
1351 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
))
1353 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
))
1355 if (PIM_DEBUG_TRACE
)
1356 zlog_debug ("Upstream %s without a path to send join, checking",
1358 pim_rpf_update (up
, NULL
);
1364 pim_upstream_hash_key (void *arg
)
1366 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1368 return jhash_2words (up
->sg
.src
.s_addr
, up
->sg
.grp
.s_addr
, 0);
1371 void pim_upstream_terminate (void)
1373 if (pim_upstream_list
)
1374 list_delete (pim_upstream_list
);
1375 pim_upstream_list
= NULL
;
1377 if (pim_upstream_hash
)
1378 hash_free (pim_upstream_hash
);
1379 pim_upstream_hash
= NULL
;
1383 pim_upstream_equal (const void *arg1
, const void *arg2
)
1385 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
1386 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
1388 if ((up1
->sg
.grp
.s_addr
== up2
->sg
.grp
.s_addr
) &&
1389 (up1
->sg
.src
.s_addr
== up2
->sg
.src
.s_addr
))
1395 /* rfc4601:section-4.2:"Data Packet Forwarding Rules" defines
1396 * the cases where kat has to be restarted on rxing traffic -
1398 * if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) {
1399 * set KeepaliveTimer(S,G) to Keepalive_Period
1400 * # Note: a register state transition or UpstreamJPState(S,G)
1401 * # transition may happen as a result of restarting
1402 * # KeepaliveTimer, and must be dealt with here.
1404 * if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND
1405 * inherited_olist(S,G) != NULL ) {
1406 * set KeepaliveTimer(S,G) to Keepalive_Period
1409 static bool pim_upstream_kat_start_ok(struct pim_upstream
*up
)
1411 /* "iif == RPF_interface(S)" check has to be done by the kernel or hw
1412 * so we will skip that here */
1413 if (pim_if_connected_to_source(up
->rpf
.source_nexthop
.interface
,
1418 if ((up
->join_state
== PIM_UPSTREAM_JOINED
) &&
1419 !pim_upstream_empty_inherited_olist(up
)) {
1420 /* XXX: I have added this RP check just for 3.2 and it's a digression from
1421 * what rfc-4601 says. Till now we were only running KAT on FHR and RP and
1422 * there is some angst around making the change to run it all routers that
1423 * maintain the (S, G) state. This is tracked via CM-13601 and MUST be
1424 * removed to handle spt turn-arounds correctly in a 3-tier clos */
1425 if (I_am_RP (up
->sg
.grp
))
1433 * Code to check and see if we've received packets on a S,G mroute
1434 * and if so to set the SPT bit appropriately
1437 pim_upstream_sg_running (void *arg
)
1439 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1441 // No packet can have arrived here if this is the case
1442 if (!up
->channel_oil
|| !up
->channel_oil
->installed
)
1444 if (PIM_DEBUG_TRACE
)
1445 zlog_debug ("%s: %s is not installed in mroute",
1446 __PRETTY_FUNCTION__
, up
->sg_str
);
1451 * This is a bit of a hack
1452 * We've noted that we should rescan but
1453 * we've missed the window for doing so in
1454 * pim_zebra.c for some reason. I am
1455 * only doing this at this point in time
1456 * to get us up and working for the moment
1458 if (up
->channel_oil
->oil_inherited_rescan
)
1460 if (PIM_DEBUG_TRACE
)
1461 zlog_debug ("%s: Handling unscanned inherited_olist for %s", __PRETTY_FUNCTION__
, up
->sg_str
);
1462 pim_upstream_inherited_olist_decide (up
);
1463 up
->channel_oil
->oil_inherited_rescan
= 0;
1465 pim_mroute_update_counters (up
->channel_oil
);
1467 // Have we seen packets?
1468 if ((up
->channel_oil
->cc
.oldpktcnt
>= up
->channel_oil
->cc
.pktcnt
) &&
1469 (up
->channel_oil
->cc
.lastused
/100 > 30))
1471 if (PIM_DEBUG_TRACE
)
1473 zlog_debug ("%s: %s old packet count is equal or lastused is greater than 30, (%ld,%ld,%lld)",
1474 __PRETTY_FUNCTION__
, up
->sg_str
,
1475 up
->channel_oil
->cc
.oldpktcnt
,
1476 up
->channel_oil
->cc
.pktcnt
,
1477 up
->channel_oil
->cc
.lastused
/100);
1482 if (pim_upstream_kat_start_ok(up
)) {
1483 /* Add a source reference to the stream if
1484 * one doesn't already exist */
1485 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
1487 if (PIM_DEBUG_TRACE
)
1488 zlog_debug ("source reference created on kat restart %s", up
->sg_str
);
1490 pim_upstream_ref(up
, PIM_UPSTREAM_FLAG_MASK_SRC_STREAM
);
1491 PIM_UPSTREAM_FLAG_SET_SRC_STREAM(up
->flags
);
1492 pim_upstream_fhr_kat_start(up
);
1494 pim_upstream_keep_alive_timer_start(up
, qpim_keep_alive_time
);
1497 if (up
->sptbit
!= PIM_UPSTREAM_SPTBIT_TRUE
)
1499 pim_upstream_set_sptbit(up
, up
->rpf
.source_nexthop
.interface
);
1505 pim_upstream_init (void)
1507 pim_upstream_sg_wheel
= wheel_init (master
, 31000, 100,
1508 pim_upstream_hash_key
,
1509 pim_upstream_sg_running
);
1510 pim_upstream_hash
= hash_create_size (8192, pim_upstream_hash_key
,
1511 pim_upstream_equal
);
1513 pim_upstream_list
= list_new ();
1514 pim_upstream_list
->del
= (void (*)(void *)) pim_upstream_free
;
1515 pim_upstream_list
->cmp
= pim_upstream_compare
;