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
.source_nexthop
.interface
,
175 up
->rpf
.rpf_addr
.u
.prefix4
,
177 if (up
->sg
.src
.s_addr
== INADDR_ANY
) {
178 /* if a (*, G) entry in the joined state is being deleted we
179 * need to notify MSDP */
184 if (up
->sg
.src
.s_addr
!= INADDR_ANY
) {
185 wheel_remove_item (pim_upstream_sg_wheel
, up
);
189 pim_upstream_remove_children (up
);
190 pim_mroute_del (up
->channel_oil
, __PRETTY_FUNCTION__
);
191 upstream_channel_oil_detach(up
);
194 list_delete (up
->sources
);
198 notice that listnode_delete() can't be moved
199 into pim_upstream_free() because the later is
200 called by list_delete_all_node()
204 listnode_delete (up
->parent
->sources
, up
);
207 listnode_delete (pim_upstream_list
, up
);
208 hash_release (pim_upstream_hash
, up
);
211 pim_msdp_up_del(&up
->sg
);
213 pim_upstream_free(up
);
217 pim_upstream_send_join (struct pim_upstream
*up
)
219 if (PIM_DEBUG_TRACE
) {
220 char rpf_str
[PREFIX_STRLEN
];
221 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_str
, sizeof(rpf_str
));
222 zlog_debug ("%s: RPF'%s=%s(%s) for Interface %s", __PRETTY_FUNCTION__
,
223 up
->sg_str
, rpf_str
, pim_upstream_state2str (up
->join_state
),
224 up
->rpf
.source_nexthop
.interface
->name
);
225 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
)) {
226 zlog_debug("%s: can't send join upstream: RPF'%s=%s",
228 up
->sg_str
, rpf_str
);
233 /* send Join(S,G) to the current upstream neighbor */
234 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
235 up
->rpf
.rpf_addr
.u
.prefix4
,
240 static int on_join_timer(struct thread
*t
)
242 struct pim_upstream
*up
;
246 up
->t_join_timer
= NULL
;
249 * In the case of a HFR we will not ahve anyone to send this to.
251 if (PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
255 * Don't send the join if the outgoing interface is a loopback
256 * But since this might change leave the join timer running
258 if (!if_is_loopback (up
->rpf
.source_nexthop
.interface
))
259 pim_upstream_send_join (up
);
261 join_timer_start(up
);
266 static void join_timer_start(struct pim_upstream
*up
)
268 if (PIM_DEBUG_PIM_EVENTS
) {
269 zlog_debug("%s: starting %d sec timer for upstream (S,G)=%s",
275 THREAD_OFF (up
->t_join_timer
);
276 THREAD_TIMER_ON(master
, up
->t_join_timer
,
278 up
, qpim_t_periodic
);
281 void pim_upstream_join_timer_restart(struct pim_upstream
*up
)
283 THREAD_OFF(up
->t_join_timer
);
284 join_timer_start(up
);
287 static void pim_upstream_join_timer_restart_msec(struct pim_upstream
*up
,
290 if (PIM_DEBUG_PIM_EVENTS
) {
291 zlog_debug("%s: restarting %d msec timer for upstream (S,G)=%s",
297 THREAD_OFF(up
->t_join_timer
);
298 THREAD_TIMER_MSEC_ON(master
, up
->t_join_timer
,
303 void pim_upstream_join_suppress(struct pim_upstream
*up
,
304 struct in_addr rpf_addr
,
307 long t_joinsuppress_msec
;
308 long join_timer_remain_msec
;
310 t_joinsuppress_msec
= MIN(pim_if_t_suppressed_msec(up
->rpf
.source_nexthop
.interface
),
313 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
315 if (PIM_DEBUG_TRACE
) {
316 char rpf_str
[INET_ADDRSTRLEN
];
317 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
318 zlog_debug("%s %s: detected Join%s to RPF'(S,G)=%s: join_timer=%ld msec t_joinsuppress=%ld msec",
319 __FILE__
, __PRETTY_FUNCTION__
,
322 join_timer_remain_msec
, t_joinsuppress_msec
);
325 if (join_timer_remain_msec
< t_joinsuppress_msec
) {
326 if (PIM_DEBUG_TRACE
) {
327 zlog_debug("%s %s: suppressing Join(S,G)=%s for %ld msec",
328 __FILE__
, __PRETTY_FUNCTION__
,
329 up
->sg_str
, t_joinsuppress_msec
);
332 pim_upstream_join_timer_restart_msec(up
, t_joinsuppress_msec
);
336 void pim_upstream_join_timer_decrease_to_t_override(const char *debug_label
,
337 struct pim_upstream
*up
,
338 struct in_addr rpf_addr
)
340 long join_timer_remain_msec
;
343 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
344 t_override_msec
= pim_if_t_override_msec(up
->rpf
.source_nexthop
.interface
);
346 if (PIM_DEBUG_TRACE
) {
347 char rpf_str
[INET_ADDRSTRLEN
];
348 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
349 zlog_debug("%s: to RPF'%s=%s: join_timer=%ld msec t_override=%d msec",
352 join_timer_remain_msec
, t_override_msec
);
355 if (join_timer_remain_msec
> t_override_msec
) {
356 if (PIM_DEBUG_TRACE
) {
357 zlog_debug("%s: decreasing (S,G)=%s join timer to t_override=%d msec",
363 pim_upstream_join_timer_restart_msec(up
, t_override_msec
);
367 static void forward_on(struct pim_upstream
*up
)
369 struct listnode
*chnode
;
370 struct listnode
*chnextnode
;
371 struct pim_interface
*pim_ifp
;
372 struct pim_ifchannel
*ch
;
374 /* scan (S,G) state */
375 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
376 pim_ifp
= ch
->interface
->info
;
380 if (ch
->upstream
!= up
)
383 if (pim_macro_chisin_oiflist(ch
))
384 pim_forward_start(ch
);
386 } /* scan iface channel list */
389 static void forward_off(struct pim_upstream
*up
)
391 struct listnode
*chnode
;
392 struct listnode
*chnextnode
;
393 struct pim_interface
*pim_ifp
;
394 struct pim_ifchannel
*ch
;
396 /* scan per-interface (S,G) state */
397 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
398 pim_ifp
= ch
->interface
->info
;
402 if (ch
->upstream
!= up
)
405 pim_forward_stop(ch
);
407 } /* scan iface channel list */
411 pim_upstream_could_register (struct pim_upstream
*up
)
413 struct pim_interface
*pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
415 if (pim_ifp
&& PIM_I_am_DR (pim_ifp
) &&
416 pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
423 pim_upstream_switch(struct pim_upstream
*up
,
424 enum pim_upstream_state new_state
)
426 enum pim_upstream_state old_state
= up
->join_state
;
428 if (PIM_DEBUG_PIM_EVENTS
) {
429 zlog_debug("%s: PIM_UPSTREAM_%s: (S,G) old: %s new: %s",
432 pim_upstream_state2str (up
->join_state
),
433 pim_upstream_state2str (new_state
));
437 * This code still needs work.
439 switch (up
->join_state
)
441 case PIM_UPSTREAM_PRUNE
:
442 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
444 up
->join_state
= new_state
;
445 up
->state_transition
= pim_time_monotonic_sec ();
448 case PIM_UPSTREAM_JOIN_PENDING
:
450 case PIM_UPSTREAM_NOTJOINED
:
451 case PIM_UPSTREAM_JOINED
:
452 up
->join_state
= new_state
;
453 if (old_state
!= new_state
)
454 up
->state_transition
= pim_time_monotonic_sec();
459 pim_upstream_update_assert_tracking_desired(up
);
461 if (new_state
== PIM_UPSTREAM_JOINED
) {
462 if (old_state
!= PIM_UPSTREAM_JOINED
)
464 int old_fhr
= PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
);
466 pim_msdp_up_join_state_changed(up
);
467 if (pim_upstream_could_register (up
))
469 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
470 if (!old_fhr
&& PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
472 pim_upstream_keep_alive_timer_start (up
, qpim_keep_alive_time
);
473 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
478 pim_upstream_send_join (up
);
479 join_timer_start (up
);
489 if (old_state
== PIM_UPSTREAM_JOINED
)
490 pim_msdp_up_join_state_changed(up
);
491 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
492 up
->rpf
.rpf_addr
.u
.prefix4
,
495 if (up
->t_join_timer
)
496 THREAD_OFF(up
->t_join_timer
);
501 pim_upstream_compare (void *arg1
, void *arg2
)
503 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
504 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
506 if (ntohl(up1
->sg
.grp
.s_addr
) < ntohl(up2
->sg
.grp
.s_addr
))
509 if (ntohl(up1
->sg
.grp
.s_addr
) > ntohl(up2
->sg
.grp
.s_addr
))
512 if (ntohl(up1
->sg
.src
.s_addr
) < ntohl(up2
->sg
.src
.s_addr
))
515 if (ntohl(up1
->sg
.src
.s_addr
) > ntohl(up2
->sg
.src
.s_addr
))
521 static struct pim_upstream
*
522 pim_upstream_new (struct prefix_sg
*sg
,
523 struct interface
*incoming
,
526 enum pim_rpf_result rpf_result
;
527 struct pim_interface
*pim_ifp
;
528 struct pim_upstream
*up
;
530 up
= XCALLOC(MTYPE_PIM_UPSTREAM
, sizeof(*up
));
532 zlog_err("%s: PIM XCALLOC(%zu) failure",
533 __PRETTY_FUNCTION__
, sizeof(*up
));
538 pim_str_sg_set (sg
, up
->sg_str
);
539 up
= hash_get (pim_upstream_hash
, up
, hash_alloc_intern
);
540 if (!pim_rp_set_upstream_addr (&up
->upstream_addr
, sg
->src
, sg
->grp
))
543 zlog_debug("%s: Received a (*,G) with no RP configured", __PRETTY_FUNCTION__
);
545 hash_release (pim_upstream_hash
, up
);
546 XFREE (MTYPE_PIM_UPSTREAM
, up
);
550 up
->parent
= pim_upstream_find_parent (up
);
551 if (up
->sg
.src
.s_addr
== INADDR_ANY
)
553 up
->sources
= list_new ();
554 up
->sources
->cmp
= pim_upstream_compare
;
559 pim_upstream_find_new_children (up
);
562 up
->t_join_timer
= NULL
;
563 up
->t_ka_timer
= NULL
;
564 up
->t_rs_timer
= NULL
;
565 up
->t_msdp_reg_timer
= NULL
;
567 up
->state_transition
= pim_time_monotonic_sec();
568 up
->channel_oil
= NULL
;
569 up
->sptbit
= PIM_UPSTREAM_SPTBIT_FALSE
;
571 up
->rpf
.source_nexthop
.interface
= NULL
;
572 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.family
= AF_INET
;
573 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
574 up
->rpf
.source_nexthop
.mrib_metric_preference
= qpim_infinite_assert_metric
.metric_preference
;
575 up
->rpf
.source_nexthop
.mrib_route_metric
= qpim_infinite_assert_metric
.route_metric
;
576 up
->rpf
.rpf_addr
.family
= AF_INET
;
577 up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
579 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
580 wheel_add_item (pim_upstream_sg_wheel
, up
);
582 rpf_result
= pim_rpf_update(up
, NULL
);
583 if (rpf_result
== PIM_RPF_FAILURE
) {
585 zlog_debug ("%s: Attempting to create upstream(%s), Unable to RPF for source", __PRETTY_FUNCTION__
,
590 listnode_delete (up
->parent
->sources
, up
);
594 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
595 wheel_remove_item (pim_upstream_sg_wheel
, up
);
597 pim_upstream_remove_children (up
);
599 list_delete (up
->sources
);
601 hash_release (pim_upstream_hash
, up
);
602 XFREE(MTYPE_PIM_UPSTREAM
, up
);
606 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
608 up
->channel_oil
= pim_channel_oil_add(&up
->sg
, pim_ifp
->mroute_vif_index
);
610 listnode_add_sort(pim_upstream_list
, up
);
613 zlog_debug ("%s: Created Upstream %s", __PRETTY_FUNCTION__
, up
->sg_str
);
618 struct pim_upstream
*pim_upstream_find(struct prefix_sg
*sg
)
620 struct pim_upstream lookup
;
621 struct pim_upstream
*up
= NULL
;
624 up
= hash_lookup (pim_upstream_hash
, &lookup
);
628 static void pim_upstream_ref(struct pim_upstream
*up
, int flags
)
634 struct pim_upstream
*pim_upstream_add(struct prefix_sg
*sg
,
635 struct interface
*incoming
,
636 int flags
, const char *name
)
638 struct pim_upstream
*up
= NULL
;
640 up
= pim_upstream_find(sg
);
642 pim_upstream_ref(up
, flags
);
646 up
= pim_upstream_new(sg
, incoming
, flags
);
652 zlog_debug("%s(%s): %s, found: %d: ref_count: %d",
653 __PRETTY_FUNCTION__
, name
,
657 zlog_debug("%s(%s): (%s) failure to create",
658 __PRETTY_FUNCTION__
, name
,
659 pim_str_sg_dump (sg
));
666 pim_upstream_evaluate_join_desired_interface (struct pim_upstream
*up
,
667 struct pim_ifchannel
*ch
)
669 struct pim_upstream
*parent
= up
->parent
;
671 if (ch
->upstream
== up
)
673 if (!pim_macro_ch_lost_assert(ch
) && pim_macro_chisin_joins_or_include(ch
))
676 if (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
))
683 if (parent
&& ch
->upstream
== parent
)
685 if (!pim_macro_ch_lost_assert (ch
) && pim_macro_chisin_joins_or_include (ch
))
693 Evaluate JoinDesired(S,G):
695 JoinDesired(S,G) is true if there is a downstream (S,G) interface I
698 inherited_olist(S,G) =
699 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
701 JoinDesired(S,G) may be affected by changes in the following:
703 pim_ifp->primary_address
705 ch->ifassert_winner_metric
707 ch->local_ifmembership
709 ch->upstream->rpf.source_nexthop.mrib_metric_preference
710 ch->upstream->rpf.source_nexthop.mrib_route_metric
711 ch->upstream->rpf.source_nexthop.interface
713 See also pim_upstream_update_join_desired() below.
715 int pim_upstream_evaluate_join_desired(struct pim_upstream
*up
)
717 struct listnode
*chnode
;
718 struct listnode
*chnextnode
;
719 struct pim_interface
*pim_ifp
;
720 struct pim_ifchannel
*ch
;
723 /* scan per-interface (S,G) state */
724 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
))
726 pim_ifp
= ch
->interface
->info
;
730 ret
+= pim_upstream_evaluate_join_desired_interface (up
, ch
);
731 } /* scan iface channel list */
733 return ret
; /* false */
737 See also pim_upstream_evaluate_join_desired() above.
739 void pim_upstream_update_join_desired(struct pim_upstream
*up
)
741 int was_join_desired
; /* boolean */
742 int is_join_desired
; /* boolean */
744 was_join_desired
= PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up
->flags
);
746 is_join_desired
= pim_upstream_evaluate_join_desired(up
);
748 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up
->flags
);
750 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up
->flags
);
752 /* switched from false to true */
753 if (is_join_desired
&& !was_join_desired
) {
754 pim_upstream_switch(up
, PIM_UPSTREAM_JOINED
);
758 /* switched from true to false */
759 if (!is_join_desired
&& was_join_desired
) {
760 pim_upstream_switch(up
, PIM_UPSTREAM_NOTJOINED
);
766 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
767 Transitions from Joined State
768 RPF'(S,G) GenID changes
770 The upstream (S,G) state machine remains in Joined state. If the
771 Join Timer is set to expire in more than t_override seconds, reset
772 it so that it expires after t_override seconds.
774 void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr
)
776 struct listnode
*up_node
;
777 struct listnode
*up_nextnode
;
778 struct pim_upstream
*up
;
781 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
783 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
)) {
785 if (PIM_DEBUG_TRACE
) {
786 char neigh_str
[INET_ADDRSTRLEN
];
787 char rpf_addr_str
[PREFIX_STRLEN
];
788 pim_inet4_dump("<neigh?>", neigh_addr
, neigh_str
, sizeof(neigh_str
));
789 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_addr_str
, sizeof(rpf_addr_str
));
790 zlog_debug("%s: matching neigh=%s against upstream (S,G)=%s joined=%d rpf_addr=%s",
792 neigh_str
, up
->sg_str
,
793 up
->join_state
== PIM_UPSTREAM_JOINED
,
797 /* consider only (S,G) upstream in Joined state */
798 if (up
->join_state
!= PIM_UPSTREAM_JOINED
)
801 /* match RPF'(S,G)=neigh_addr */
802 if (up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
!= neigh_addr
.s_addr
)
805 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
811 void pim_upstream_rpf_interface_changed(struct pim_upstream
*up
,
812 struct interface
*old_rpf_ifp
)
814 struct listnode
*chnode
;
815 struct listnode
*chnextnode
;
816 struct pim_ifchannel
*ch
;
817 struct pim_interface
*pim_ifp
;
819 /* search all ifchannels */
820 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
822 pim_ifp
= ch
->interface
->info
;
826 if (ch
->upstream
!= up
)
829 if (ch
->ifassert_state
== PIM_IFASSERT_I_AM_LOSER
) {
831 /* RPF_interface(S) was NOT I */
832 (old_rpf_ifp
== ch
->interface
)
834 /* RPF_interface(S) stopped being I */
835 (ch
->upstream
->rpf
.source_nexthop
.interface
!= ch
->interface
)
837 assert_action_a5(ch
);
839 } /* PIM_IFASSERT_I_AM_LOSER */
841 pim_ifchannel_update_assert_tracking_desired(ch
);
845 void pim_upstream_update_could_assert(struct pim_upstream
*up
)
847 struct listnode
*chnode
;
848 struct listnode
*chnextnode
;
849 struct pim_interface
*pim_ifp
;
850 struct pim_ifchannel
*ch
;
852 /* scan per-interface (S,G) state */
853 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
854 pim_ifp
= ch
->interface
->info
;
858 if (ch
->upstream
!= up
)
861 pim_ifchannel_update_could_assert(ch
);
862 } /* scan iface channel list */
865 void pim_upstream_update_my_assert_metric(struct pim_upstream
*up
)
867 struct listnode
*chnode
;
868 struct listnode
*chnextnode
;
869 struct pim_interface
*pim_ifp
;
870 struct pim_ifchannel
*ch
;
872 /* scan per-interface (S,G) state */
873 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
874 pim_ifp
= ch
->interface
->info
;
878 if (ch
->upstream
!= up
)
881 pim_ifchannel_update_my_assert_metric(ch
);
883 } /* scan iface channel list */
886 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
)
888 struct listnode
*chnode
;
889 struct listnode
*chnextnode
;
890 struct pim_interface
*pim_ifp
;
891 struct pim_ifchannel
*ch
;
893 /* scan per-interface (S,G) state */
894 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
895 pim_ifp
= ch
->interface
->info
;
899 if (ch
->upstream
!= up
)
902 pim_ifchannel_update_assert_tracking_desired(ch
);
904 } /* scan iface channel list */
907 /* When kat is stopped CouldRegister goes to false so we need to
908 * transition the (S, G) on FHR to NI state and remove reg tunnel
910 static void pim_upstream_fhr_kat_expiry(struct pim_upstream
*up
)
912 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
916 zlog_debug ("kat expired on %s; clear fhr reg state", up
->sg_str
);
918 /* stop reg-stop timer */
919 THREAD_OFF(up
->t_rs_timer
);
920 /* remove regiface from the OIL if it is there*/
921 pim_channel_del_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
922 /* move to "not-joined" */
923 up
->join_state
= PIM_UPSTREAM_NOTJOINED
;
924 PIM_UPSTREAM_FLAG_UNSET_FHR(up
->flags
);
927 /* When kat is started CouldRegister can go to true. And if it does we
928 * need to transition the (S, G) on FHR to JOINED state and add reg tunnel
930 static void pim_upstream_fhr_kat_start(struct pim_upstream
*up
)
932 if (pim_upstream_could_register(up
)) {
934 zlog_debug ("kat started on %s; set fhr reg state to joined", up
->sg_str
);
936 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
937 if (up
->join_state
== PIM_UPSTREAM_NOTJOINED
) {
938 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
939 up
->join_state
= PIM_UPSTREAM_JOINED
;
945 * On an RP, the PMBR value must be cleared when the
946 * Keepalive Timer expires
947 * KAT expiry indicates that flow is inactive. If the flow was created or
948 * maintained by activity now is the time to deref it.
951 pim_upstream_keep_alive_timer (struct thread
*t
)
953 struct pim_upstream
*up
;
956 up
->t_ka_timer
= NULL
;
958 if (I_am_RP (up
->sg
.grp
))
960 pim_br_clear_pmbr (&up
->sg
);
962 * We need to do more here :)
963 * But this is the start.
967 /* source is no longer active - pull the SA from MSDP's cache */
968 pim_msdp_sa_local_del(&up
->sg
);
970 /* if entry was created because of activity we need to deref it */
971 if (PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
973 pim_upstream_fhr_kat_expiry(up
);
975 zlog_debug ("kat expired on %s; remove stream reference", up
->sg_str
);
976 PIM_UPSTREAM_FLAG_UNSET_SRC_STREAM(up
->flags
);
977 pim_upstream_del(up
, __PRETTY_FUNCTION__
);
984 pim_upstream_keep_alive_timer_start (struct pim_upstream
*up
,
987 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
)) {
989 zlog_debug ("kat start on %s with no stream reference", up
->sg_str
);
991 THREAD_OFF (up
->t_ka_timer
);
992 THREAD_TIMER_ON (master
,
994 pim_upstream_keep_alive_timer
,
997 /* any time keepalive is started against a SG we will have to
998 * re-evaluate our active source database */
999 pim_msdp_sa_local_update(up
);
1002 /* MSDP on RP needs to know if a source is registerable to this RP */
1004 pim_upstream_msdp_reg_timer(struct thread
*t
)
1006 struct pim_upstream
*up
;
1009 up
->t_msdp_reg_timer
= NULL
;
1011 /* source is no longer active - pull the SA from MSDP's cache */
1012 pim_msdp_sa_local_del(&up
->sg
);
1016 pim_upstream_msdp_reg_timer_start(struct pim_upstream
*up
)
1018 THREAD_OFF(up
->t_msdp_reg_timer
);
1019 THREAD_TIMER_ON(master
, up
->t_msdp_reg_timer
,
1020 pim_upstream_msdp_reg_timer
, up
, PIM_MSDP_REG_RXED_PERIOD
);
1022 pim_msdp_sa_local_update(up
);
1026 * 4.2.1 Last-Hop Switchover to the SPT
1028 * In Sparse-Mode PIM, last-hop routers join the shared tree towards the
1029 * RP. Once traffic from sources to joined groups arrives at a last-hop
1030 * router, it has the option of switching to receive the traffic on a
1031 * shortest path tree (SPT).
1033 * The decision for a router to switch to the SPT is controlled as
1037 * CheckSwitchToSpt(S,G) {
1038 * if ( ( pim_include(*,G) (-) pim_exclude(S,G)
1039 * (+) pim_include(S,G) != NULL )
1040 * AND SwitchToSptDesired(S,G) ) {
1041 * # Note: Restarting the KAT will result in the SPT switch
1042 * set KeepaliveTimer(S,G) to Keepalive_Period
1046 * SwitchToSptDesired(S,G) is a policy function that is implementation
1047 * defined. An "infinite threshold" policy can be implemented by making
1048 * SwitchToSptDesired(S,G) return false all the time. A "switch on
1049 * first packet" policy can be implemented by making
1050 * SwitchToSptDesired(S,G) return true once a single packet has been
1051 * received for the source and group.
1054 pim_upstream_switch_to_spt_desired (struct prefix_sg
*sg
)
1056 if (I_am_RP (sg
->grp
))
1063 pim_upstream_is_sg_rpt (struct pim_upstream
*up
)
1065 struct listnode
*chnode
;
1066 struct pim_ifchannel
*ch
;
1068 for (ALL_LIST_ELEMENTS_RO(pim_ifchannel_list
, chnode
, ch
))
1070 if ((ch
->upstream
== up
) &&
1071 (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
)))
1078 * After receiving a packet set SPTbit:
1080 * Update_SPTbit(S,G,iif) {
1081 * if ( iif == RPF_interface(S)
1082 * AND JoinDesired(S,G) == TRUE
1083 * AND ( DirectlyConnected(S) == TRUE
1084 * OR RPF_interface(S) != RPF_interface(RP(G))
1085 * OR inherited_olist(S,G,rpt) == NULL
1086 * OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1087 * ( RPF'(S,G) != NULL ) )
1088 * OR ( I_Am_Assert_Loser(S,G,iif) ) {
1089 * Set SPTbit(S,G) to TRUE
1094 pim_upstream_set_sptbit (struct pim_upstream
*up
, struct interface
*incoming
)
1096 struct pim_rpf
*grpf
= NULL
;
1098 // iif == RPF_interfvace(S)
1099 if (up
->rpf
.source_nexthop
.interface
!= incoming
)
1101 if (PIM_DEBUG_TRACE
)
1102 zlog_debug ("%s: Incoming Interface: %s is different than RPF_interface(S) %s",
1103 __PRETTY_FUNCTION__
, incoming
->name
, up
->rpf
.source_nexthop
.interface
->name
);
1107 // AND JoinDesired(S,G) == TRUE
1110 // DirectlyConnected(S) == TRUE
1111 if (pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
1113 if (PIM_DEBUG_TRACE
)
1114 zlog_debug ("%s: %s is directly connected to the source", __PRETTY_FUNCTION__
,
1116 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1120 // OR RPF_interface(S) != RPF_interface(RP(G))
1121 grpf
= RP(up
->sg
.grp
);
1122 if (!grpf
|| up
->rpf
.source_nexthop
.interface
!= grpf
->source_nexthop
.interface
)
1124 if (PIM_DEBUG_TRACE
)
1125 zlog_debug ("%s: %s RPF_interface(S) != RPF_interface(RP(G))",
1126 __PRETTY_FUNCTION__
, up
->sg_str
);
1127 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1131 // OR inherited_olist(S,G,rpt) == NULL
1132 if (pim_upstream_is_sg_rpt(up
) && pim_upstream_empty_inherited_olist(up
))
1134 if (PIM_DEBUG_TRACE
)
1135 zlog_debug ("%s: %s OR inherited_olist(S,G,rpt) == NULL", __PRETTY_FUNCTION__
,
1137 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1141 // OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1142 // ( RPF'(S,G) != NULL ) )
1143 if (up
->parent
&& pim_rpf_is_same (&up
->rpf
, &up
->parent
->rpf
))
1145 if (PIM_DEBUG_TRACE
)
1146 zlog_debug ("%s: %s RPF'(S,G) is the same as RPF'(*,G)", __PRETTY_FUNCTION__
,
1148 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1156 pim_upstream_state2str (enum pim_upstream_state join_state
)
1160 case PIM_UPSTREAM_NOTJOINED
:
1163 case PIM_UPSTREAM_JOINED
:
1166 case PIM_UPSTREAM_JOIN_PENDING
:
1167 return "JoinPending";
1169 case PIM_UPSTREAM_PRUNE
:
1177 pim_upstream_register_stop_timer (struct thread
*t
)
1179 struct pim_interface
*pim_ifp
;
1180 struct pim_upstream
*up
;
1181 struct pim_rpf
*rpg
;
1183 up
= THREAD_ARG (t
);
1185 up
->t_rs_timer
= NULL
;
1187 if (PIM_DEBUG_TRACE
)
1189 zlog_debug ("%s: (S,G)=%s upstream register stop timer %s",
1190 __PRETTY_FUNCTION__
, up
->sg_str
,
1191 pim_upstream_state2str(up
->join_state
));
1194 switch (up
->join_state
)
1196 case PIM_UPSTREAM_JOIN_PENDING
:
1197 up
->join_state
= PIM_UPSTREAM_JOINED
;
1198 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
1200 case PIM_UPSTREAM_JOINED
:
1202 case PIM_UPSTREAM_PRUNE
:
1203 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1206 if (PIM_DEBUG_TRACE
)
1207 zlog_debug ("%s: Interface: %s is not configured for pim",
1208 __PRETTY_FUNCTION__
, up
->rpf
.source_nexthop
.interface
->name
);
1211 up
->join_state
= PIM_UPSTREAM_JOIN_PENDING
;
1212 pim_upstream_start_register_stop_timer (up
, 1);
1214 if (((up
->channel_oil
->cc
.lastused
/100) > PIM_KEEPALIVE_PERIOD
) &&
1215 (I_am_RP (up
->sg
.grp
)))
1217 if (PIM_DEBUG_TRACE
)
1218 zlog_debug ("%s: Stop sending the register, because I am the RP and we haven't seen a packet in a while", __PRETTY_FUNCTION__
);
1221 rpg
= RP (up
->sg
.grp
);
1222 memset (&ip_hdr
, 0, sizeof (struct ip
));
1223 ip_hdr
.ip_p
= PIM_IP_PROTO_PIM
;
1226 ip_hdr
.ip_src
= up
->sg
.src
;
1227 ip_hdr
.ip_dst
= up
->sg
.grp
;
1228 ip_hdr
.ip_len
= htons (20);
1229 // checksum is broken
1230 pim_register_send ((uint8_t *)&ip_hdr
, sizeof (struct ip
),
1231 pim_ifp
->primary_address
, rpg
, 1, up
);
1241 pim_upstream_start_register_stop_timer (struct pim_upstream
*up
, int null_register
)
1247 THREAD_TIMER_OFF (up
->t_rs_timer
);
1248 up
->t_rs_timer
= NULL
;
1253 uint32_t lower
= (0.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1254 uint32_t upper
= (1.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1255 time
= lower
+ (random () % (upper
- lower
+ 1)) - PIM_REGISTER_PROBE_PERIOD
;
1258 time
= PIM_REGISTER_PROBE_PERIOD
;
1260 if (PIM_DEBUG_TRACE
)
1262 zlog_debug ("%s: (S,G)=%s Starting upstream register stop timer %d",
1263 __PRETTY_FUNCTION__
, up
->sg_str
, time
);
1265 THREAD_TIMER_ON (master
, up
->t_rs_timer
,
1266 pim_upstream_register_stop_timer
,
1271 pim_upstream_inherited_olist_decide (struct pim_upstream
*up
)
1273 struct pim_interface
*pim_ifp
;
1274 struct listnode
*chnextnode
;
1275 struct pim_ifchannel
*ch
;
1276 struct listnode
*chnode
;
1277 int output_intf
= 0;
1279 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1280 if (pim_ifp
&& !up
->channel_oil
)
1281 up
->channel_oil
= pim_channel_oil_add (&up
->sg
, pim_ifp
->mroute_vif_index
);
1283 for (ALL_LIST_ELEMENTS (pim_ifchannel_list
, chnode
, chnextnode
, ch
))
1285 pim_ifp
= ch
->interface
->info
;
1289 if (pim_upstream_evaluate_join_desired_interface (up
, ch
))
1291 pim_channel_add_oif (up
->channel_oil
, ch
->interface
, PIM_OIF_FLAG_PROTO_PIM
);
1300 * For a given upstream, determine the inherited_olist
1303 * inherited_olist(S,G,rpt) =
1304 * ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
1305 * (+) ( pim_include(*,G) (-) pim_exclude(S,G))
1306 * (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) )
1308 * inherited_olist(S,G) =
1309 * inherited_olist(S,G,rpt) (+)
1310 * joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
1312 * return 1 if there are any output interfaces
1313 * return 0 if there are not any output interfaces
1316 pim_upstream_inherited_olist (struct pim_upstream
*up
)
1318 int output_intf
= pim_upstream_inherited_olist_decide (up
);
1321 * If we have output_intf switch state to Join and work like normal
1322 * If we don't have an output_intf that means we are probably a
1323 * switch on a stick so turn on forwarding to just accept the
1324 * incoming packets so we don't bother the other stuff!
1327 pim_upstream_switch (up
, PIM_UPSTREAM_JOINED
);
1335 pim_upstream_empty_inherited_olist (struct pim_upstream
*up
)
1337 return pim_channel_oil_empty (up
->channel_oil
);
1341 * When we have a new neighbor,
1342 * find upstreams that don't have their rpf_addr
1343 * set and see if the new neighbor allows
1344 * the join to be sent
1347 pim_upstream_find_new_rpf (void)
1349 struct listnode
*up_node
;
1350 struct listnode
*up_nextnode
;
1351 struct pim_upstream
*up
;
1354 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
1356 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
))
1358 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
))
1360 if (PIM_DEBUG_TRACE
)
1361 zlog_debug ("Upstream %s without a path to send join, checking",
1363 pim_rpf_update (up
, NULL
);
1369 pim_upstream_hash_key (void *arg
)
1371 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1373 return jhash_2words (up
->sg
.src
.s_addr
, up
->sg
.grp
.s_addr
, 0);
1376 void pim_upstream_terminate (void)
1378 if (pim_upstream_list
)
1379 list_delete (pim_upstream_list
);
1380 pim_upstream_list
= NULL
;
1382 if (pim_upstream_hash
)
1383 hash_free (pim_upstream_hash
);
1384 pim_upstream_hash
= NULL
;
1388 pim_upstream_equal (const void *arg1
, const void *arg2
)
1390 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
1391 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
1393 if ((up1
->sg
.grp
.s_addr
== up2
->sg
.grp
.s_addr
) &&
1394 (up1
->sg
.src
.s_addr
== up2
->sg
.src
.s_addr
))
1400 /* rfc4601:section-4.2:"Data Packet Forwarding Rules" defines
1401 * the cases where kat has to be restarted on rxing traffic -
1403 * if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) {
1404 * set KeepaliveTimer(S,G) to Keepalive_Period
1405 * # Note: a register state transition or UpstreamJPState(S,G)
1406 * # transition may happen as a result of restarting
1407 * # KeepaliveTimer, and must be dealt with here.
1409 * if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND
1410 * inherited_olist(S,G) != NULL ) {
1411 * set KeepaliveTimer(S,G) to Keepalive_Period
1414 static bool pim_upstream_kat_start_ok(struct pim_upstream
*up
)
1416 /* "iif == RPF_interface(S)" check has to be done by the kernel or hw
1417 * so we will skip that here */
1418 if (pim_if_connected_to_source(up
->rpf
.source_nexthop
.interface
,
1423 if ((up
->join_state
== PIM_UPSTREAM_JOINED
) &&
1424 !pim_upstream_empty_inherited_olist(up
)) {
1425 /* XXX: I have added this RP check just for 3.2 and it's a digression from
1426 * what rfc-4601 says. Till now we were only running KAT on FHR and RP and
1427 * there is some angst around making the change to run it all routers that
1428 * maintain the (S, G) state. This is tracked via CM-13601 and MUST be
1429 * removed to handle spt turn-arounds correctly in a 3-tier clos */
1430 if (I_am_RP (up
->sg
.grp
))
1438 * Code to check and see if we've received packets on a S,G mroute
1439 * and if so to set the SPT bit appropriately
1442 pim_upstream_sg_running (void *arg
)
1444 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1446 // No packet can have arrived here if this is the case
1447 if (!up
->channel_oil
|| !up
->channel_oil
->installed
)
1449 if (PIM_DEBUG_TRACE
)
1450 zlog_debug ("%s: %s is not installed in mroute",
1451 __PRETTY_FUNCTION__
, up
->sg_str
);
1456 * This is a bit of a hack
1457 * We've noted that we should rescan but
1458 * we've missed the window for doing so in
1459 * pim_zebra.c for some reason. I am
1460 * only doing this at this point in time
1461 * to get us up and working for the moment
1463 if (up
->channel_oil
->oil_inherited_rescan
)
1465 if (PIM_DEBUG_TRACE
)
1466 zlog_debug ("%s: Handling unscanned inherited_olist for %s", __PRETTY_FUNCTION__
, up
->sg_str
);
1467 pim_upstream_inherited_olist_decide (up
);
1468 up
->channel_oil
->oil_inherited_rescan
= 0;
1470 pim_mroute_update_counters (up
->channel_oil
);
1472 // Have we seen packets?
1473 if ((up
->channel_oil
->cc
.oldpktcnt
>= up
->channel_oil
->cc
.pktcnt
) &&
1474 (up
->channel_oil
->cc
.lastused
/100 > 30))
1476 if (PIM_DEBUG_TRACE
)
1478 zlog_debug ("%s: %s old packet count is equal or lastused is greater than 30, (%ld,%ld,%lld)",
1479 __PRETTY_FUNCTION__
, up
->sg_str
,
1480 up
->channel_oil
->cc
.oldpktcnt
,
1481 up
->channel_oil
->cc
.pktcnt
,
1482 up
->channel_oil
->cc
.lastused
/100);
1487 if (pim_upstream_kat_start_ok(up
)) {
1488 /* Add a source reference to the stream if
1489 * one doesn't already exist */
1490 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
1492 if (PIM_DEBUG_TRACE
)
1493 zlog_debug ("source reference created on kat restart %s", up
->sg_str
);
1495 pim_upstream_ref(up
, PIM_UPSTREAM_FLAG_MASK_SRC_STREAM
);
1496 PIM_UPSTREAM_FLAG_SET_SRC_STREAM(up
->flags
);
1497 pim_upstream_fhr_kat_start(up
);
1499 pim_upstream_keep_alive_timer_start(up
, qpim_keep_alive_time
);
1502 if (up
->sptbit
!= PIM_UPSTREAM_SPTBIT_TRUE
)
1504 pim_upstream_set_sptbit(up
, up
->rpf
.source_nexthop
.interface
);
1510 pim_upstream_init (void)
1512 pim_upstream_sg_wheel
= wheel_init (master
, 31000, 100,
1513 pim_upstream_hash_key
,
1514 pim_upstream_sg_running
);
1515 pim_upstream_hash
= hash_create_size (8192, pim_upstream_hash_key
,
1516 pim_upstream_equal
);
1518 pim_upstream_list
= list_new ();
1519 pim_upstream_list
->del
= (void (*)(void *)) pim_upstream_free
;
1520 pim_upstream_list
->cmp
= pim_upstream_compare
;