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
)
339 long join_timer_remain_msec
;
342 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
343 t_override_msec
= pim_if_t_override_msec(up
->rpf
.source_nexthop
.interface
);
345 if (PIM_DEBUG_TRACE
) {
346 char rpf_str
[INET_ADDRSTRLEN
];
347 pim_inet4_dump("<rpf?>", up
->rpf
.rpf_addr
.u
.prefix4
, rpf_str
, sizeof(rpf_str
));
348 zlog_debug("%s: to RPF'%s=%s: join_timer=%ld msec t_override=%d msec",
351 join_timer_remain_msec
, t_override_msec
);
354 if (join_timer_remain_msec
> t_override_msec
) {
355 if (PIM_DEBUG_TRACE
) {
356 zlog_debug("%s: decreasing (S,G)=%s join timer to t_override=%d msec",
362 pim_upstream_join_timer_restart_msec(up
, t_override_msec
);
366 static void forward_on(struct pim_upstream
*up
)
368 struct listnode
*chnode
;
369 struct listnode
*chnextnode
;
370 struct pim_interface
*pim_ifp
;
371 struct pim_ifchannel
*ch
;
373 /* scan (S,G) state */
374 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
375 pim_ifp
= ch
->interface
->info
;
379 if (ch
->upstream
!= up
)
382 if (pim_macro_chisin_oiflist(ch
))
383 pim_forward_start(ch
);
385 } /* scan iface channel list */
388 static void forward_off(struct pim_upstream
*up
)
390 struct listnode
*chnode
;
391 struct listnode
*chnextnode
;
392 struct pim_interface
*pim_ifp
;
393 struct pim_ifchannel
*ch
;
395 /* scan per-interface (S,G) state */
396 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
397 pim_ifp
= ch
->interface
->info
;
401 if (ch
->upstream
!= up
)
404 pim_forward_stop(ch
);
406 } /* scan iface channel list */
410 pim_upstream_could_register (struct pim_upstream
*up
)
412 struct pim_interface
*pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
414 if (pim_ifp
&& PIM_I_am_DR (pim_ifp
) &&
415 pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
422 pim_upstream_switch(struct pim_upstream
*up
,
423 enum pim_upstream_state new_state
)
425 enum pim_upstream_state old_state
= up
->join_state
;
427 if (PIM_DEBUG_PIM_EVENTS
) {
428 zlog_debug("%s: PIM_UPSTREAM_%s: (S,G) old: %s new: %s",
431 pim_upstream_state2str (up
->join_state
),
432 pim_upstream_state2str (new_state
));
436 * This code still needs work.
438 switch (up
->join_state
)
440 case PIM_UPSTREAM_PRUNE
:
441 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
443 up
->join_state
= new_state
;
444 up
->state_transition
= pim_time_monotonic_sec ();
447 case PIM_UPSTREAM_JOIN_PENDING
:
449 case PIM_UPSTREAM_NOTJOINED
:
450 case PIM_UPSTREAM_JOINED
:
451 up
->join_state
= new_state
;
452 if (old_state
!= new_state
)
453 up
->state_transition
= pim_time_monotonic_sec();
458 pim_upstream_update_assert_tracking_desired(up
);
460 if (new_state
== PIM_UPSTREAM_JOINED
) {
461 if (old_state
!= PIM_UPSTREAM_JOINED
)
463 int old_fhr
= PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
);
465 pim_msdp_up_join_state_changed(up
);
466 if (pim_upstream_could_register (up
))
468 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
469 if (!old_fhr
&& PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
471 pim_upstream_keep_alive_timer_start (up
, qpim_keep_alive_time
);
472 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
477 pim_upstream_send_join (up
);
478 join_timer_start (up
);
488 if (old_state
== PIM_UPSTREAM_JOINED
)
489 pim_msdp_up_join_state_changed(up
);
490 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
491 up
->rpf
.rpf_addr
.u
.prefix4
,
494 if (up
->t_join_timer
)
495 THREAD_OFF(up
->t_join_timer
);
500 pim_upstream_compare (void *arg1
, void *arg2
)
502 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
503 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
505 if (ntohl(up1
->sg
.grp
.s_addr
) < ntohl(up2
->sg
.grp
.s_addr
))
508 if (ntohl(up1
->sg
.grp
.s_addr
) > ntohl(up2
->sg
.grp
.s_addr
))
511 if (ntohl(up1
->sg
.src
.s_addr
) < ntohl(up2
->sg
.src
.s_addr
))
514 if (ntohl(up1
->sg
.src
.s_addr
) > ntohl(up2
->sg
.src
.s_addr
))
520 static struct pim_upstream
*
521 pim_upstream_new (struct prefix_sg
*sg
,
522 struct interface
*incoming
,
525 enum pim_rpf_result rpf_result
;
526 struct pim_interface
*pim_ifp
;
527 struct pim_upstream
*up
;
529 up
= XCALLOC(MTYPE_PIM_UPSTREAM
, sizeof(*up
));
531 zlog_err("%s: PIM XCALLOC(%zu) failure",
532 __PRETTY_FUNCTION__
, sizeof(*up
));
537 pim_str_sg_set (sg
, up
->sg_str
);
538 up
= hash_get (pim_upstream_hash
, up
, hash_alloc_intern
);
539 if (!pim_rp_set_upstream_addr (&up
->upstream_addr
, sg
->src
, sg
->grp
))
542 zlog_debug("%s: Received a (*,G) with no RP configured", __PRETTY_FUNCTION__
);
544 hash_release (pim_upstream_hash
, up
);
545 XFREE (MTYPE_PIM_UPSTREAM
, up
);
549 up
->parent
= pim_upstream_find_parent (up
);
550 if (up
->sg
.src
.s_addr
== INADDR_ANY
)
552 up
->sources
= list_new ();
553 up
->sources
->cmp
= pim_upstream_compare
;
558 pim_upstream_find_new_children (up
);
561 up
->t_join_timer
= NULL
;
562 up
->t_ka_timer
= NULL
;
563 up
->t_rs_timer
= NULL
;
564 up
->t_msdp_reg_timer
= NULL
;
566 up
->state_transition
= pim_time_monotonic_sec();
567 up
->channel_oil
= NULL
;
568 up
->sptbit
= PIM_UPSTREAM_SPTBIT_FALSE
;
570 up
->rpf
.source_nexthop
.interface
= NULL
;
571 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.family
= AF_INET
;
572 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
573 up
->rpf
.source_nexthop
.mrib_metric_preference
= qpim_infinite_assert_metric
.metric_preference
;
574 up
->rpf
.source_nexthop
.mrib_route_metric
= qpim_infinite_assert_metric
.route_metric
;
575 up
->rpf
.rpf_addr
.family
= AF_INET
;
576 up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
578 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
579 wheel_add_item (pim_upstream_sg_wheel
, up
);
581 rpf_result
= pim_rpf_update(up
, NULL
);
582 if (rpf_result
== PIM_RPF_FAILURE
) {
584 zlog_debug ("%s: Attempting to create upstream(%s), Unable to RPF for source", __PRETTY_FUNCTION__
,
589 listnode_delete (up
->parent
->sources
, up
);
593 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
594 wheel_remove_item (pim_upstream_sg_wheel
, up
);
596 pim_upstream_remove_children (up
);
598 list_delete (up
->sources
);
600 hash_release (pim_upstream_hash
, up
);
601 XFREE(MTYPE_PIM_UPSTREAM
, up
);
605 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
607 up
->channel_oil
= pim_channel_oil_add(&up
->sg
, pim_ifp
->mroute_vif_index
);
609 listnode_add_sort(pim_upstream_list
, up
);
612 zlog_debug ("%s: Created Upstream %s", __PRETTY_FUNCTION__
, up
->sg_str
);
617 struct pim_upstream
*pim_upstream_find(struct prefix_sg
*sg
)
619 struct pim_upstream lookup
;
620 struct pim_upstream
*up
= NULL
;
623 up
= hash_lookup (pim_upstream_hash
, &lookup
);
627 static void pim_upstream_ref(struct pim_upstream
*up
, int flags
)
633 struct pim_upstream
*pim_upstream_add(struct prefix_sg
*sg
,
634 struct interface
*incoming
,
635 int flags
, const char *name
)
637 struct pim_upstream
*up
= NULL
;
639 up
= pim_upstream_find(sg
);
641 pim_upstream_ref(up
, flags
);
645 up
= pim_upstream_new(sg
, incoming
, flags
);
651 zlog_debug("%s(%s): %s, found: %d: ref_count: %d",
652 __PRETTY_FUNCTION__
, name
,
656 zlog_debug("%s(%s): (%s) failure to create",
657 __PRETTY_FUNCTION__
, name
,
658 pim_str_sg_dump (sg
));
665 pim_upstream_evaluate_join_desired_interface (struct pim_upstream
*up
,
666 struct pim_ifchannel
*ch
)
668 struct pim_upstream
*parent
= up
->parent
;
670 if (ch
->upstream
== up
)
672 if (!pim_macro_ch_lost_assert(ch
) && pim_macro_chisin_joins_or_include(ch
))
675 if (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
))
682 if (parent
&& ch
->upstream
== parent
)
684 if (!pim_macro_ch_lost_assert (ch
) && pim_macro_chisin_joins_or_include (ch
))
692 Evaluate JoinDesired(S,G):
694 JoinDesired(S,G) is true if there is a downstream (S,G) interface I
697 inherited_olist(S,G) =
698 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
700 JoinDesired(S,G) may be affected by changes in the following:
702 pim_ifp->primary_address
704 ch->ifassert_winner_metric
706 ch->local_ifmembership
708 ch->upstream->rpf.source_nexthop.mrib_metric_preference
709 ch->upstream->rpf.source_nexthop.mrib_route_metric
710 ch->upstream->rpf.source_nexthop.interface
712 See also pim_upstream_update_join_desired() below.
714 int pim_upstream_evaluate_join_desired(struct pim_upstream
*up
)
716 struct listnode
*chnode
;
717 struct listnode
*chnextnode
;
718 struct pim_interface
*pim_ifp
;
719 struct pim_ifchannel
*ch
;
722 /* scan per-interface (S,G) state */
723 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
))
725 pim_ifp
= ch
->interface
->info
;
729 ret
+= pim_upstream_evaluate_join_desired_interface (up
, ch
);
730 } /* scan iface channel list */
732 return ret
; /* false */
736 See also pim_upstream_evaluate_join_desired() above.
738 void pim_upstream_update_join_desired(struct pim_upstream
*up
)
740 int was_join_desired
; /* boolean */
741 int is_join_desired
; /* boolean */
743 was_join_desired
= PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up
->flags
);
745 is_join_desired
= pim_upstream_evaluate_join_desired(up
);
747 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up
->flags
);
749 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up
->flags
);
751 /* switched from false to true */
752 if (is_join_desired
&& !was_join_desired
) {
753 pim_upstream_switch(up
, PIM_UPSTREAM_JOINED
);
757 /* switched from true to false */
758 if (!is_join_desired
&& was_join_desired
) {
759 pim_upstream_switch(up
, PIM_UPSTREAM_NOTJOINED
);
765 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
766 Transitions from Joined State
767 RPF'(S,G) GenID changes
769 The upstream (S,G) state machine remains in Joined state. If the
770 Join Timer is set to expire in more than t_override seconds, reset
771 it so that it expires after t_override seconds.
773 void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr
)
775 struct listnode
*up_node
;
776 struct listnode
*up_nextnode
;
777 struct pim_upstream
*up
;
780 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
782 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
)) {
784 if (PIM_DEBUG_TRACE
) {
785 char neigh_str
[INET_ADDRSTRLEN
];
786 char rpf_addr_str
[PREFIX_STRLEN
];
787 pim_inet4_dump("<neigh?>", neigh_addr
, neigh_str
, sizeof(neigh_str
));
788 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_addr_str
, sizeof(rpf_addr_str
));
789 zlog_debug("%s: matching neigh=%s against upstream (S,G)=%s joined=%d rpf_addr=%s",
791 neigh_str
, up
->sg_str
,
792 up
->join_state
== PIM_UPSTREAM_JOINED
,
796 /* consider only (S,G) upstream in Joined state */
797 if (up
->join_state
!= PIM_UPSTREAM_JOINED
)
800 /* match RPF'(S,G)=neigh_addr */
801 if (up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
!= neigh_addr
.s_addr
)
804 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
810 void pim_upstream_rpf_interface_changed(struct pim_upstream
*up
,
811 struct interface
*old_rpf_ifp
)
813 struct listnode
*chnode
;
814 struct listnode
*chnextnode
;
815 struct pim_ifchannel
*ch
;
816 struct pim_interface
*pim_ifp
;
818 /* search all ifchannels */
819 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
821 pim_ifp
= ch
->interface
->info
;
825 if (ch
->upstream
!= up
)
828 if (ch
->ifassert_state
== PIM_IFASSERT_I_AM_LOSER
) {
830 /* RPF_interface(S) was NOT I */
831 (old_rpf_ifp
== ch
->interface
)
833 /* RPF_interface(S) stopped being I */
834 (ch
->upstream
->rpf
.source_nexthop
.interface
!= ch
->interface
)
836 assert_action_a5(ch
);
838 } /* PIM_IFASSERT_I_AM_LOSER */
840 pim_ifchannel_update_assert_tracking_desired(ch
);
844 void pim_upstream_update_could_assert(struct pim_upstream
*up
)
846 struct listnode
*chnode
;
847 struct listnode
*chnextnode
;
848 struct pim_interface
*pim_ifp
;
849 struct pim_ifchannel
*ch
;
851 /* scan per-interface (S,G) state */
852 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
853 pim_ifp
= ch
->interface
->info
;
857 if (ch
->upstream
!= up
)
860 pim_ifchannel_update_could_assert(ch
);
861 } /* scan iface channel list */
864 void pim_upstream_update_my_assert_metric(struct pim_upstream
*up
)
866 struct listnode
*chnode
;
867 struct listnode
*chnextnode
;
868 struct pim_interface
*pim_ifp
;
869 struct pim_ifchannel
*ch
;
871 /* scan per-interface (S,G) state */
872 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
873 pim_ifp
= ch
->interface
->info
;
877 if (ch
->upstream
!= up
)
880 pim_ifchannel_update_my_assert_metric(ch
);
882 } /* scan iface channel list */
885 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
)
887 struct listnode
*chnode
;
888 struct listnode
*chnextnode
;
889 struct pim_interface
*pim_ifp
;
890 struct pim_ifchannel
*ch
;
892 /* scan per-interface (S,G) state */
893 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
894 pim_ifp
= ch
->interface
->info
;
898 if (ch
->upstream
!= up
)
901 pim_ifchannel_update_assert_tracking_desired(ch
);
903 } /* scan iface channel list */
906 /* When kat is stopped CouldRegister goes to false so we need to
907 * transition the (S, G) on FHR to NI state and remove reg tunnel
909 static void pim_upstream_fhr_kat_expiry(struct pim_upstream
*up
)
911 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
915 zlog_debug ("kat expired on %s; clear fhr reg state", up
->sg_str
);
917 /* stop reg-stop timer */
918 THREAD_OFF(up
->t_rs_timer
);
919 /* remove regiface from the OIL if it is there*/
920 pim_channel_del_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
921 /* move to "not-joined" */
922 up
->join_state
= PIM_UPSTREAM_NOTJOINED
;
923 PIM_UPSTREAM_FLAG_UNSET_FHR(up
->flags
);
926 /* When kat is started CouldRegister can go to true. And if it does we
927 * need to transition the (S, G) on FHR to JOINED state and add reg tunnel
929 static void pim_upstream_fhr_kat_start(struct pim_upstream
*up
)
931 if (pim_upstream_could_register(up
)) {
933 zlog_debug ("kat started on %s; set fhr reg state to joined", up
->sg_str
);
935 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
936 if (up
->join_state
== PIM_UPSTREAM_NOTJOINED
) {
937 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
938 up
->join_state
= PIM_UPSTREAM_JOINED
;
944 * On an RP, the PMBR value must be cleared when the
945 * Keepalive Timer expires
946 * KAT expiry indicates that flow is inactive. If the flow was created or
947 * maintained by activity now is the time to deref it.
950 pim_upstream_keep_alive_timer (struct thread
*t
)
952 struct pim_upstream
*up
;
955 up
->t_ka_timer
= NULL
;
957 if (I_am_RP (up
->sg
.grp
))
959 pim_br_clear_pmbr (&up
->sg
);
961 * We need to do more here :)
962 * But this is the start.
966 /* source is no longer active - pull the SA from MSDP's cache */
967 pim_msdp_sa_local_del(&up
->sg
);
969 /* if entry was created because of activity we need to deref it */
970 if (PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
972 pim_upstream_fhr_kat_expiry(up
);
974 zlog_debug ("kat expired on %s; remove stream reference", up
->sg_str
);
975 PIM_UPSTREAM_FLAG_UNSET_SRC_STREAM(up
->flags
);
976 pim_upstream_del(up
, __PRETTY_FUNCTION__
);
983 pim_upstream_keep_alive_timer_start (struct pim_upstream
*up
,
986 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
)) {
988 zlog_debug ("kat start on %s with no stream reference", up
->sg_str
);
990 THREAD_OFF (up
->t_ka_timer
);
991 THREAD_TIMER_ON (master
,
993 pim_upstream_keep_alive_timer
,
996 /* any time keepalive is started against a SG we will have to
997 * re-evaluate our active source database */
998 pim_msdp_sa_local_update(up
);
1001 /* MSDP on RP needs to know if a source is registerable to this RP */
1003 pim_upstream_msdp_reg_timer(struct thread
*t
)
1005 struct pim_upstream
*up
;
1008 up
->t_msdp_reg_timer
= NULL
;
1010 /* source is no longer active - pull the SA from MSDP's cache */
1011 pim_msdp_sa_local_del(&up
->sg
);
1015 pim_upstream_msdp_reg_timer_start(struct pim_upstream
*up
)
1017 THREAD_OFF(up
->t_msdp_reg_timer
);
1018 THREAD_TIMER_ON(master
, up
->t_msdp_reg_timer
,
1019 pim_upstream_msdp_reg_timer
, up
, PIM_MSDP_REG_RXED_PERIOD
);
1021 pim_msdp_sa_local_update(up
);
1025 * 4.2.1 Last-Hop Switchover to the SPT
1027 * In Sparse-Mode PIM, last-hop routers join the shared tree towards the
1028 * RP. Once traffic from sources to joined groups arrives at a last-hop
1029 * router, it has the option of switching to receive the traffic on a
1030 * shortest path tree (SPT).
1032 * The decision for a router to switch to the SPT is controlled as
1036 * CheckSwitchToSpt(S,G) {
1037 * if ( ( pim_include(*,G) (-) pim_exclude(S,G)
1038 * (+) pim_include(S,G) != NULL )
1039 * AND SwitchToSptDesired(S,G) ) {
1040 * # Note: Restarting the KAT will result in the SPT switch
1041 * set KeepaliveTimer(S,G) to Keepalive_Period
1045 * SwitchToSptDesired(S,G) is a policy function that is implementation
1046 * defined. An "infinite threshold" policy can be implemented by making
1047 * SwitchToSptDesired(S,G) return false all the time. A "switch on
1048 * first packet" policy can be implemented by making
1049 * SwitchToSptDesired(S,G) return true once a single packet has been
1050 * received for the source and group.
1053 pim_upstream_switch_to_spt_desired (struct prefix_sg
*sg
)
1055 if (I_am_RP (sg
->grp
))
1062 pim_upstream_is_sg_rpt (struct pim_upstream
*up
)
1064 struct listnode
*chnode
;
1065 struct pim_ifchannel
*ch
;
1067 for (ALL_LIST_ELEMENTS_RO(pim_ifchannel_list
, chnode
, ch
))
1069 if ((ch
->upstream
== up
) &&
1070 (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
)))
1077 * After receiving a packet set SPTbit:
1079 * Update_SPTbit(S,G,iif) {
1080 * if ( iif == RPF_interface(S)
1081 * AND JoinDesired(S,G) == TRUE
1082 * AND ( DirectlyConnected(S) == TRUE
1083 * OR RPF_interface(S) != RPF_interface(RP(G))
1084 * OR inherited_olist(S,G,rpt) == NULL
1085 * OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1086 * ( RPF'(S,G) != NULL ) )
1087 * OR ( I_Am_Assert_Loser(S,G,iif) ) {
1088 * Set SPTbit(S,G) to TRUE
1093 pim_upstream_set_sptbit (struct pim_upstream
*up
, struct interface
*incoming
)
1095 struct pim_rpf
*grpf
= NULL
;
1097 // iif == RPF_interfvace(S)
1098 if (up
->rpf
.source_nexthop
.interface
!= incoming
)
1100 if (PIM_DEBUG_TRACE
)
1101 zlog_debug ("%s: Incoming Interface: %s is different than RPF_interface(S) %s",
1102 __PRETTY_FUNCTION__
, incoming
->name
, up
->rpf
.source_nexthop
.interface
->name
);
1106 // AND JoinDesired(S,G) == TRUE
1109 // DirectlyConnected(S) == TRUE
1110 if (pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
1112 if (PIM_DEBUG_TRACE
)
1113 zlog_debug ("%s: %s is directly connected to the source", __PRETTY_FUNCTION__
,
1115 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1119 // OR RPF_interface(S) != RPF_interface(RP(G))
1120 grpf
= RP(up
->sg
.grp
);
1121 if (!grpf
|| up
->rpf
.source_nexthop
.interface
!= grpf
->source_nexthop
.interface
)
1123 if (PIM_DEBUG_TRACE
)
1124 zlog_debug ("%s: %s RPF_interface(S) != RPF_interface(RP(G))",
1125 __PRETTY_FUNCTION__
, up
->sg_str
);
1126 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1130 // OR inherited_olist(S,G,rpt) == NULL
1131 if (pim_upstream_is_sg_rpt(up
) && pim_upstream_empty_inherited_olist(up
))
1133 if (PIM_DEBUG_TRACE
)
1134 zlog_debug ("%s: %s OR inherited_olist(S,G,rpt) == NULL", __PRETTY_FUNCTION__
,
1136 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1140 // OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1141 // ( RPF'(S,G) != NULL ) )
1142 if (up
->parent
&& pim_rpf_is_same (&up
->rpf
, &up
->parent
->rpf
))
1144 if (PIM_DEBUG_TRACE
)
1145 zlog_debug ("%s: %s RPF'(S,G) is the same as RPF'(*,G)", __PRETTY_FUNCTION__
,
1147 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1155 pim_upstream_state2str (enum pim_upstream_state join_state
)
1159 case PIM_UPSTREAM_NOTJOINED
:
1162 case PIM_UPSTREAM_JOINED
:
1165 case PIM_UPSTREAM_JOIN_PENDING
:
1166 return "JoinPending";
1168 case PIM_UPSTREAM_PRUNE
:
1176 pim_upstream_register_stop_timer (struct thread
*t
)
1178 struct pim_interface
*pim_ifp
;
1179 struct pim_upstream
*up
;
1180 struct pim_rpf
*rpg
;
1182 up
= THREAD_ARG (t
);
1184 up
->t_rs_timer
= NULL
;
1186 if (PIM_DEBUG_TRACE
)
1188 zlog_debug ("%s: (S,G)=%s upstream register stop timer %s",
1189 __PRETTY_FUNCTION__
, up
->sg_str
,
1190 pim_upstream_state2str(up
->join_state
));
1193 switch (up
->join_state
)
1195 case PIM_UPSTREAM_JOIN_PENDING
:
1196 up
->join_state
= PIM_UPSTREAM_JOINED
;
1197 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
1199 case PIM_UPSTREAM_JOINED
:
1201 case PIM_UPSTREAM_PRUNE
:
1202 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1205 if (PIM_DEBUG_TRACE
)
1206 zlog_debug ("%s: Interface: %s is not configured for pim",
1207 __PRETTY_FUNCTION__
, up
->rpf
.source_nexthop
.interface
->name
);
1210 up
->join_state
= PIM_UPSTREAM_JOIN_PENDING
;
1211 pim_upstream_start_register_stop_timer (up
, 1);
1213 if (((up
->channel_oil
->cc
.lastused
/100) > PIM_KEEPALIVE_PERIOD
) &&
1214 (I_am_RP (up
->sg
.grp
)))
1216 if (PIM_DEBUG_TRACE
)
1217 zlog_debug ("%s: Stop sending the register, because I am the RP and we haven't seen a packet in a while", __PRETTY_FUNCTION__
);
1220 rpg
= RP (up
->sg
.grp
);
1221 memset (&ip_hdr
, 0, sizeof (struct ip
));
1222 ip_hdr
.ip_p
= PIM_IP_PROTO_PIM
;
1225 ip_hdr
.ip_src
= up
->sg
.src
;
1226 ip_hdr
.ip_dst
= up
->sg
.grp
;
1227 ip_hdr
.ip_len
= htons (20);
1228 // checksum is broken
1229 pim_register_send ((uint8_t *)&ip_hdr
, sizeof (struct ip
),
1230 pim_ifp
->primary_address
, rpg
, 1, up
);
1240 pim_upstream_start_register_stop_timer (struct pim_upstream
*up
, int null_register
)
1246 THREAD_TIMER_OFF (up
->t_rs_timer
);
1247 up
->t_rs_timer
= NULL
;
1252 uint32_t lower
= (0.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1253 uint32_t upper
= (1.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1254 time
= lower
+ (random () % (upper
- lower
+ 1)) - PIM_REGISTER_PROBE_PERIOD
;
1257 time
= PIM_REGISTER_PROBE_PERIOD
;
1259 if (PIM_DEBUG_TRACE
)
1261 zlog_debug ("%s: (S,G)=%s Starting upstream register stop timer %d",
1262 __PRETTY_FUNCTION__
, up
->sg_str
, time
);
1264 THREAD_TIMER_ON (master
, up
->t_rs_timer
,
1265 pim_upstream_register_stop_timer
,
1270 pim_upstream_inherited_olist_decide (struct pim_upstream
*up
)
1272 struct pim_interface
*pim_ifp
;
1273 struct listnode
*chnextnode
;
1274 struct pim_ifchannel
*ch
;
1275 struct listnode
*chnode
;
1276 int output_intf
= 0;
1278 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1279 if (pim_ifp
&& !up
->channel_oil
)
1280 up
->channel_oil
= pim_channel_oil_add (&up
->sg
, pim_ifp
->mroute_vif_index
);
1282 for (ALL_LIST_ELEMENTS (pim_ifchannel_list
, chnode
, chnextnode
, ch
))
1284 pim_ifp
= ch
->interface
->info
;
1288 if (pim_upstream_evaluate_join_desired_interface (up
, ch
))
1290 int flag
= PIM_OIF_FLAG_PROTO_PIM
;
1292 if (ch
->sg
.src
.s_addr
== INADDR_ANY
&& ch
->upstream
!= up
)
1293 flag
= PIM_OIF_FLAG_PROTO_STAR
;
1294 pim_channel_add_oif (up
->channel_oil
, ch
->interface
, flag
);
1303 * For a given upstream, determine the inherited_olist
1306 * inherited_olist(S,G,rpt) =
1307 * ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
1308 * (+) ( pim_include(*,G) (-) pim_exclude(S,G))
1309 * (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) )
1311 * inherited_olist(S,G) =
1312 * inherited_olist(S,G,rpt) (+)
1313 * joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
1315 * return 1 if there are any output interfaces
1316 * return 0 if there are not any output interfaces
1319 pim_upstream_inherited_olist (struct pim_upstream
*up
)
1321 int output_intf
= pim_upstream_inherited_olist_decide (up
);
1324 * If we have output_intf switch state to Join and work like normal
1325 * If we don't have an output_intf that means we are probably a
1326 * switch on a stick so turn on forwarding to just accept the
1327 * incoming packets so we don't bother the other stuff!
1330 pim_upstream_switch (up
, PIM_UPSTREAM_JOINED
);
1338 pim_upstream_empty_inherited_olist (struct pim_upstream
*up
)
1340 return pim_channel_oil_empty (up
->channel_oil
);
1344 * When we have a new neighbor,
1345 * find upstreams that don't have their rpf_addr
1346 * set and see if the new neighbor allows
1347 * the join to be sent
1350 pim_upstream_find_new_rpf (void)
1352 struct listnode
*up_node
;
1353 struct listnode
*up_nextnode
;
1354 struct pim_upstream
*up
;
1357 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
1359 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
))
1361 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
))
1363 if (PIM_DEBUG_TRACE
)
1364 zlog_debug ("Upstream %s without a path to send join, checking",
1366 pim_rpf_update (up
, NULL
);
1372 pim_upstream_hash_key (void *arg
)
1374 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1376 return jhash_2words (up
->sg
.src
.s_addr
, up
->sg
.grp
.s_addr
, 0);
1379 void pim_upstream_terminate (void)
1381 if (pim_upstream_list
)
1382 list_delete (pim_upstream_list
);
1383 pim_upstream_list
= NULL
;
1385 if (pim_upstream_hash
)
1386 hash_free (pim_upstream_hash
);
1387 pim_upstream_hash
= NULL
;
1391 pim_upstream_equal (const void *arg1
, const void *arg2
)
1393 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
1394 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
1396 if ((up1
->sg
.grp
.s_addr
== up2
->sg
.grp
.s_addr
) &&
1397 (up1
->sg
.src
.s_addr
== up2
->sg
.src
.s_addr
))
1403 /* rfc4601:section-4.2:"Data Packet Forwarding Rules" defines
1404 * the cases where kat has to be restarted on rxing traffic -
1406 * if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) {
1407 * set KeepaliveTimer(S,G) to Keepalive_Period
1408 * # Note: a register state transition or UpstreamJPState(S,G)
1409 * # transition may happen as a result of restarting
1410 * # KeepaliveTimer, and must be dealt with here.
1412 * if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND
1413 * inherited_olist(S,G) != NULL ) {
1414 * set KeepaliveTimer(S,G) to Keepalive_Period
1417 static bool pim_upstream_kat_start_ok(struct pim_upstream
*up
)
1419 /* "iif == RPF_interface(S)" check has to be done by the kernel or hw
1420 * so we will skip that here */
1421 if (pim_if_connected_to_source(up
->rpf
.source_nexthop
.interface
,
1426 if ((up
->join_state
== PIM_UPSTREAM_JOINED
) &&
1427 !pim_upstream_empty_inherited_olist(up
)) {
1428 /* XXX: I have added this RP check just for 3.2 and it's a digression from
1429 * what rfc-4601 says. Till now we were only running KAT on FHR and RP and
1430 * there is some angst around making the change to run it all routers that
1431 * maintain the (S, G) state. This is tracked via CM-13601 and MUST be
1432 * removed to handle spt turn-arounds correctly in a 3-tier clos */
1433 if (I_am_RP (up
->sg
.grp
))
1441 * Code to check and see if we've received packets on a S,G mroute
1442 * and if so to set the SPT bit appropriately
1445 pim_upstream_sg_running (void *arg
)
1447 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1449 // No packet can have arrived here if this is the case
1450 if (!up
->channel_oil
|| !up
->channel_oil
->installed
)
1452 if (PIM_DEBUG_TRACE
)
1453 zlog_debug ("%s: %s is not installed in mroute",
1454 __PRETTY_FUNCTION__
, up
->sg_str
);
1459 * This is a bit of a hack
1460 * We've noted that we should rescan but
1461 * we've missed the window for doing so in
1462 * pim_zebra.c for some reason. I am
1463 * only doing this at this point in time
1464 * to get us up and working for the moment
1466 if (up
->channel_oil
->oil_inherited_rescan
)
1468 if (PIM_DEBUG_TRACE
)
1469 zlog_debug ("%s: Handling unscanned inherited_olist for %s", __PRETTY_FUNCTION__
, up
->sg_str
);
1470 pim_upstream_inherited_olist_decide (up
);
1471 up
->channel_oil
->oil_inherited_rescan
= 0;
1473 pim_mroute_update_counters (up
->channel_oil
);
1475 // Have we seen packets?
1476 if ((up
->channel_oil
->cc
.oldpktcnt
>= up
->channel_oil
->cc
.pktcnt
) &&
1477 (up
->channel_oil
->cc
.lastused
/100 > 30))
1479 if (PIM_DEBUG_TRACE
)
1481 zlog_debug ("%s: %s old packet count is equal or lastused is greater than 30, (%ld,%ld,%lld)",
1482 __PRETTY_FUNCTION__
, up
->sg_str
,
1483 up
->channel_oil
->cc
.oldpktcnt
,
1484 up
->channel_oil
->cc
.pktcnt
,
1485 up
->channel_oil
->cc
.lastused
/100);
1490 if (pim_upstream_kat_start_ok(up
)) {
1491 /* Add a source reference to the stream if
1492 * one doesn't already exist */
1493 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
1495 if (PIM_DEBUG_TRACE
)
1496 zlog_debug ("source reference created on kat restart %s", up
->sg_str
);
1498 pim_upstream_ref(up
, PIM_UPSTREAM_FLAG_MASK_SRC_STREAM
);
1499 PIM_UPSTREAM_FLAG_SET_SRC_STREAM(up
->flags
);
1500 pim_upstream_fhr_kat_start(up
);
1502 pim_upstream_keep_alive_timer_start(up
, qpim_keep_alive_time
);
1505 if (up
->sptbit
!= PIM_UPSTREAM_SPTBIT_TRUE
)
1507 pim_upstream_set_sptbit(up
, up
->rpf
.source_nexthop
.interface
);
1513 pim_upstream_init (void)
1515 pim_upstream_sg_wheel
= wheel_init (master
, 31000, 100,
1516 pim_upstream_hash_key
,
1517 pim_upstream_sg_running
);
1518 pim_upstream_hash
= hash_create_size (8192, pim_upstream_hash_key
,
1519 pim_upstream_equal
);
1521 pim_upstream_list
= list_new ();
1522 pim_upstream_list
->del
= (void (*)(void *)) pim_upstream_free
;
1523 pim_upstream_list
->cmp
= pim_upstream_compare
;