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,
24 #include "zebra/rib.h"
41 #include "pim_iface.h"
43 #include "pim_zlookup.h"
44 #include "pim_upstream.h"
45 #include "pim_ifchannel.h"
46 #include "pim_neighbor.h"
48 #include "pim_zebra.h"
50 #include "pim_macro.h"
53 #include "pim_register.h"
56 struct hash
*pim_upstream_hash
= NULL
;
57 struct list
*pim_upstream_list
= NULL
;
58 struct timer_wheel
*pim_upstream_sg_wheel
= NULL
;
60 static void join_timer_start(struct pim_upstream
*up
);
61 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
);
64 * A (*,G) or a (*,*) is going away
65 * remove the parent pointer from
66 * those pointing at us
69 pim_upstream_remove_children (struct pim_upstream
*up
)
71 struct pim_upstream
*child
;
76 while (!list_isempty (up
->sources
))
78 child
= listnode_head (up
->sources
);
80 listnode_delete (up
->sources
, child
);
85 * A (*,G) or a (*,*) is being created
86 * Find the children that would point
90 pim_upstream_find_new_children (struct pim_upstream
*up
)
92 struct pim_upstream
*child
;
93 struct listnode
*ch_node
;
95 if ((up
->sg
.src
.s_addr
!= INADDR_ANY
) &&
96 (up
->sg
.grp
.s_addr
!= INADDR_ANY
))
99 if ((up
->sg
.src
.s_addr
== INADDR_ANY
) &&
100 (up
->sg
.grp
.s_addr
== INADDR_ANY
))
103 for (ALL_LIST_ELEMENTS_RO (pim_upstream_list
, ch_node
, child
))
105 if ((up
->sg
.grp
.s_addr
!= INADDR_ANY
) &&
106 (child
->sg
.grp
.s_addr
== up
->sg
.grp
.s_addr
) &&
110 listnode_add_sort (up
->sources
, child
);
116 * If we have a (*,*) || (S,*) there is no parent
117 * If we have a (S,G), find the (*,G)
118 * If we have a (*,G), find the (*,*)
120 static struct pim_upstream
*
121 pim_upstream_find_parent (struct pim_upstream
*child
)
123 struct prefix_sg any
= child
->sg
;
124 struct pim_upstream
*up
= NULL
;
127 if ((child
->sg
.src
.s_addr
!= INADDR_ANY
) &&
128 (child
->sg
.grp
.s_addr
!= INADDR_ANY
))
130 any
.src
.s_addr
= INADDR_ANY
;
131 up
= pim_upstream_find (&any
);
134 listnode_add (up
->sources
, child
);
142 void pim_upstream_free(struct pim_upstream
*up
)
144 XFREE(MTYPE_PIM_UPSTREAM
, up
);
147 static void upstream_channel_oil_detach(struct pim_upstream
*up
)
149 if (up
->channel_oil
) {
150 pim_channel_oil_del(up
->channel_oil
);
151 up
->channel_oil
= NULL
;
156 pim_upstream_del(struct pim_upstream
*up
, const char *name
)
158 bool notify_msdp
= false;
161 zlog_debug ("%s(%s): Delete %s ref count: %d",
162 __PRETTY_FUNCTION__
, name
, up
->sg_str
, up
->ref_count
);
166 if (up
->ref_count
>= 1)
169 THREAD_OFF(up
->t_join_timer
);
170 THREAD_OFF(up
->t_ka_timer
);
171 THREAD_OFF(up
->t_rs_timer
);
172 THREAD_OFF(up
->t_msdp_reg_timer
);
174 if (up
->join_state
== PIM_UPSTREAM_JOINED
) {
175 pim_joinprune_send (up
->rpf
.source_nexthop
.interface
,
176 up
->rpf
.rpf_addr
.u
.prefix4
,
178 if (up
->sg
.src
.s_addr
== INADDR_ANY
) {
179 /* if a (*, G) entry in the joined state is being deleted we
180 * need to notify MSDP */
185 if (up
->sg
.src
.s_addr
!= INADDR_ANY
) {
186 wheel_remove_item (pim_upstream_sg_wheel
, up
);
190 pim_upstream_remove_children (up
);
191 pim_mroute_del (up
->channel_oil
, __PRETTY_FUNCTION__
);
192 upstream_channel_oil_detach(up
);
195 list_delete (up
->sources
);
199 notice that listnode_delete() can't be moved
200 into pim_upstream_free() because the later is
201 called by list_delete_all_node()
205 listnode_delete (up
->parent
->sources
, up
);
208 listnode_delete (pim_upstream_list
, up
);
209 hash_release (pim_upstream_hash
, up
);
212 pim_msdp_up_del(&up
->sg
);
214 pim_upstream_free(up
);
218 pim_upstream_send_join (struct pim_upstream
*up
)
220 if (PIM_DEBUG_TRACE
) {
221 char rpf_str
[PREFIX_STRLEN
];
222 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_str
, sizeof(rpf_str
));
223 zlog_debug ("%s: RPF'%s=%s(%s) for Interface %s", __PRETTY_FUNCTION__
,
224 up
->sg_str
, rpf_str
, pim_upstream_state2str (up
->join_state
),
225 up
->rpf
.source_nexthop
.interface
->name
);
226 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
)) {
227 zlog_debug("%s: can't send join upstream: RPF'%s=%s",
229 up
->sg_str
, rpf_str
);
234 /* send Join(S,G) to the current upstream neighbor */
235 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
236 up
->rpf
.rpf_addr
.u
.prefix4
,
241 static int on_join_timer(struct thread
*t
)
243 struct pim_upstream
*up
;
247 up
->t_join_timer
= NULL
;
250 * In the case of a HFR we will not ahve anyone to send this to.
252 if (PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
256 * Don't send the join if the outgoing interface is a loopback
257 * But since this might change leave the join timer running
259 if (!if_is_loopback (up
->rpf
.source_nexthop
.interface
))
260 pim_upstream_send_join (up
);
262 join_timer_start(up
);
267 static void join_timer_start(struct pim_upstream
*up
)
269 if (PIM_DEBUG_PIM_EVENTS
) {
270 zlog_debug("%s: starting %d sec timer for upstream (S,G)=%s",
276 THREAD_OFF (up
->t_join_timer
);
277 THREAD_TIMER_ON(master
, up
->t_join_timer
,
279 up
, qpim_t_periodic
);
282 void pim_upstream_join_timer_restart(struct pim_upstream
*up
)
284 THREAD_OFF(up
->t_join_timer
);
285 join_timer_start(up
);
288 static void pim_upstream_join_timer_restart_msec(struct pim_upstream
*up
,
291 if (PIM_DEBUG_PIM_EVENTS
) {
292 zlog_debug("%s: restarting %d msec timer for upstream (S,G)=%s",
298 THREAD_OFF(up
->t_join_timer
);
299 THREAD_TIMER_MSEC_ON(master
, up
->t_join_timer
,
304 void pim_upstream_join_suppress(struct pim_upstream
*up
,
305 struct in_addr rpf_addr
,
308 long t_joinsuppress_msec
;
309 long join_timer_remain_msec
;
311 t_joinsuppress_msec
= MIN(pim_if_t_suppressed_msec(up
->rpf
.source_nexthop
.interface
),
314 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
316 if (PIM_DEBUG_TRACE
) {
317 char rpf_str
[INET_ADDRSTRLEN
];
318 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
319 zlog_debug("%s %s: detected Join%s to RPF'(S,G)=%s: join_timer=%ld msec t_joinsuppress=%ld msec",
320 __FILE__
, __PRETTY_FUNCTION__
,
323 join_timer_remain_msec
, t_joinsuppress_msec
);
326 if (join_timer_remain_msec
< t_joinsuppress_msec
) {
327 if (PIM_DEBUG_TRACE
) {
328 zlog_debug("%s %s: suppressing Join(S,G)=%s for %ld msec",
329 __FILE__
, __PRETTY_FUNCTION__
,
330 up
->sg_str
, t_joinsuppress_msec
);
333 pim_upstream_join_timer_restart_msec(up
, t_joinsuppress_msec
);
337 void pim_upstream_join_timer_decrease_to_t_override(const char *debug_label
,
338 struct pim_upstream
*up
,
339 struct in_addr rpf_addr
)
341 long join_timer_remain_msec
;
344 join_timer_remain_msec
= pim_time_timer_remain_msec(up
->t_join_timer
);
345 t_override_msec
= pim_if_t_override_msec(up
->rpf
.source_nexthop
.interface
);
347 if (PIM_DEBUG_TRACE
) {
348 char rpf_str
[INET_ADDRSTRLEN
];
349 pim_inet4_dump("<rpf?>", rpf_addr
, rpf_str
, sizeof(rpf_str
));
350 zlog_debug("%s: to RPF'%s=%s: join_timer=%ld msec t_override=%d msec",
353 join_timer_remain_msec
, t_override_msec
);
356 if (join_timer_remain_msec
> t_override_msec
) {
357 if (PIM_DEBUG_TRACE
) {
358 zlog_debug("%s: decreasing (S,G)=%s join timer to t_override=%d msec",
364 pim_upstream_join_timer_restart_msec(up
, t_override_msec
);
368 static void forward_on(struct pim_upstream
*up
)
370 struct listnode
*chnode
;
371 struct listnode
*chnextnode
;
372 struct pim_interface
*pim_ifp
;
373 struct pim_ifchannel
*ch
;
375 /* scan (S,G) state */
376 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
377 pim_ifp
= ch
->interface
->info
;
381 if (ch
->upstream
!= up
)
384 if (pim_macro_chisin_oiflist(ch
))
385 pim_forward_start(ch
);
387 } /* scan iface channel list */
390 static void forward_off(struct pim_upstream
*up
)
392 struct listnode
*chnode
;
393 struct listnode
*chnextnode
;
394 struct pim_interface
*pim_ifp
;
395 struct pim_ifchannel
*ch
;
397 /* scan per-interface (S,G) state */
398 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
399 pim_ifp
= ch
->interface
->info
;
403 if (ch
->upstream
!= up
)
406 pim_forward_stop(ch
);
408 } /* scan iface channel list */
412 pim_upstream_could_register (struct pim_upstream
*up
)
414 struct pim_interface
*pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
416 if (pim_ifp
&& PIM_I_am_DR (pim_ifp
) &&
417 pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
424 pim_upstream_switch(struct pim_upstream
*up
,
425 enum pim_upstream_state new_state
)
427 enum pim_upstream_state old_state
= up
->join_state
;
429 if (PIM_DEBUG_PIM_EVENTS
) {
430 zlog_debug("%s: PIM_UPSTREAM_%s: (S,G) old: %s new: %s",
433 pim_upstream_state2str (up
->join_state
),
434 pim_upstream_state2str (new_state
));
438 * This code still needs work.
440 switch (up
->join_state
)
442 case PIM_UPSTREAM_PRUNE
:
443 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
445 up
->join_state
= new_state
;
446 up
->state_transition
= pim_time_monotonic_sec ();
449 case PIM_UPSTREAM_JOIN_PENDING
:
451 case PIM_UPSTREAM_NOTJOINED
:
452 case PIM_UPSTREAM_JOINED
:
453 up
->join_state
= new_state
;
454 if (old_state
!= new_state
)
455 up
->state_transition
= pim_time_monotonic_sec();
460 pim_upstream_update_assert_tracking_desired(up
);
462 if (new_state
== PIM_UPSTREAM_JOINED
) {
463 if (old_state
!= PIM_UPSTREAM_JOINED
)
465 int old_fhr
= PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
);
467 pim_msdp_up_join_state_changed(up
);
468 if (pim_upstream_could_register (up
))
470 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
471 if (!old_fhr
&& PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
473 pim_upstream_keep_alive_timer_start (up
, qpim_keep_alive_time
);
474 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
479 pim_upstream_send_join (up
);
480 join_timer_start (up
);
490 if (old_state
== PIM_UPSTREAM_JOINED
)
491 pim_msdp_up_join_state_changed(up
);
492 pim_joinprune_send(up
->rpf
.source_nexthop
.interface
,
493 up
->rpf
.rpf_addr
.u
.prefix4
,
496 if (up
->t_join_timer
)
497 THREAD_OFF(up
->t_join_timer
);
502 pim_upstream_compare (void *arg1
, void *arg2
)
504 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
505 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
507 if (ntohl(up1
->sg
.grp
.s_addr
) < ntohl(up2
->sg
.grp
.s_addr
))
510 if (ntohl(up1
->sg
.grp
.s_addr
) > ntohl(up2
->sg
.grp
.s_addr
))
513 if (ntohl(up1
->sg
.src
.s_addr
) < ntohl(up2
->sg
.src
.s_addr
))
516 if (ntohl(up1
->sg
.src
.s_addr
) > ntohl(up2
->sg
.src
.s_addr
))
522 static struct pim_upstream
*
523 pim_upstream_new (struct prefix_sg
*sg
,
524 struct interface
*incoming
,
527 enum pim_rpf_result rpf_result
;
528 struct pim_interface
*pim_ifp
;
529 struct pim_upstream
*up
;
531 up
= XCALLOC(MTYPE_PIM_UPSTREAM
, sizeof(*up
));
533 zlog_err("%s: PIM XCALLOC(%zu) failure",
534 __PRETTY_FUNCTION__
, sizeof(*up
));
539 pim_str_sg_set (sg
, up
->sg_str
);
540 up
= hash_get (pim_upstream_hash
, up
, hash_alloc_intern
);
541 if (!pim_rp_set_upstream_addr (&up
->upstream_addr
, sg
->src
, sg
->grp
))
544 zlog_debug("%s: Received a (*,G) with no RP configured", __PRETTY_FUNCTION__
);
546 hash_release (pim_upstream_hash
, up
);
547 XFREE (MTYPE_PIM_UPSTREAM
, up
);
551 up
->parent
= pim_upstream_find_parent (up
);
552 if (up
->sg
.src
.s_addr
== INADDR_ANY
)
554 up
->sources
= list_new ();
555 up
->sources
->cmp
= pim_upstream_compare
;
560 pim_upstream_find_new_children (up
);
563 up
->t_join_timer
= NULL
;
564 up
->t_ka_timer
= NULL
;
565 up
->t_rs_timer
= NULL
;
566 up
->t_msdp_reg_timer
= NULL
;
568 up
->state_transition
= pim_time_monotonic_sec();
569 up
->channel_oil
= NULL
;
570 up
->sptbit
= PIM_UPSTREAM_SPTBIT_FALSE
;
572 up
->rpf
.source_nexthop
.interface
= NULL
;
573 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.family
= AF_INET
;
574 up
->rpf
.source_nexthop
.mrib_nexthop_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
575 up
->rpf
.source_nexthop
.mrib_metric_preference
= qpim_infinite_assert_metric
.metric_preference
;
576 up
->rpf
.source_nexthop
.mrib_route_metric
= qpim_infinite_assert_metric
.route_metric
;
577 up
->rpf
.rpf_addr
.family
= AF_INET
;
578 up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
= PIM_NET_INADDR_ANY
;
580 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
581 wheel_add_item (pim_upstream_sg_wheel
, up
);
583 rpf_result
= pim_rpf_update(up
, NULL
);
584 if (rpf_result
== PIM_RPF_FAILURE
) {
586 zlog_debug ("%s: Attempting to create upstream(%s), Unable to RPF for source", __PRETTY_FUNCTION__
,
591 listnode_delete (up
->parent
->sources
, up
);
595 if (up
->sg
.src
.s_addr
!= INADDR_ANY
)
596 wheel_remove_item (pim_upstream_sg_wheel
, up
);
598 pim_upstream_remove_children (up
);
600 list_delete (up
->sources
);
602 hash_release (pim_upstream_hash
, up
);
603 XFREE(MTYPE_PIM_UPSTREAM
, up
);
607 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
609 up
->channel_oil
= pim_channel_oil_add(&up
->sg
, pim_ifp
->mroute_vif_index
);
611 listnode_add_sort(pim_upstream_list
, up
);
614 zlog_debug ("%s: Created Upstream %s", __PRETTY_FUNCTION__
, up
->sg_str
);
619 struct pim_upstream
*pim_upstream_find(struct prefix_sg
*sg
)
621 struct pim_upstream lookup
;
622 struct pim_upstream
*up
= NULL
;
625 up
= hash_lookup (pim_upstream_hash
, &lookup
);
629 static void pim_upstream_ref(struct pim_upstream
*up
, int flags
)
635 struct pim_upstream
*pim_upstream_add(struct prefix_sg
*sg
,
636 struct interface
*incoming
,
637 int flags
, const char *name
)
639 struct pim_upstream
*up
= NULL
;
641 up
= pim_upstream_find(sg
);
643 pim_upstream_ref(up
, flags
);
647 up
= pim_upstream_new(sg
, incoming
, flags
);
653 zlog_debug("%s(%s): %s, found: %d: ref_count: %d",
654 __PRETTY_FUNCTION__
, name
,
658 zlog_debug("%s(%s): (%s) failure to create",
659 __PRETTY_FUNCTION__
, name
,
660 pim_str_sg_dump (sg
));
667 pim_upstream_evaluate_join_desired_interface (struct pim_upstream
*up
,
668 struct pim_ifchannel
*ch
)
670 struct pim_upstream
*parent
= up
->parent
;
672 if (ch
->upstream
== up
)
674 if (!pim_macro_ch_lost_assert(ch
) && pim_macro_chisin_joins_or_include(ch
))
677 if (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
))
684 if (parent
&& ch
->upstream
== parent
)
686 if (!pim_macro_ch_lost_assert (ch
) && pim_macro_chisin_joins_or_include (ch
))
694 Evaluate JoinDesired(S,G):
696 JoinDesired(S,G) is true if there is a downstream (S,G) interface I
699 inherited_olist(S,G) =
700 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
702 JoinDesired(S,G) may be affected by changes in the following:
704 pim_ifp->primary_address
706 ch->ifassert_winner_metric
708 ch->local_ifmembership
710 ch->upstream->rpf.source_nexthop.mrib_metric_preference
711 ch->upstream->rpf.source_nexthop.mrib_route_metric
712 ch->upstream->rpf.source_nexthop.interface
714 See also pim_upstream_update_join_desired() below.
716 int pim_upstream_evaluate_join_desired(struct pim_upstream
*up
)
718 struct listnode
*chnode
;
719 struct listnode
*chnextnode
;
720 struct pim_interface
*pim_ifp
;
721 struct pim_ifchannel
*ch
;
724 /* scan per-interface (S,G) state */
725 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
))
727 pim_ifp
= ch
->interface
->info
;
731 ret
+= pim_upstream_evaluate_join_desired_interface (up
, ch
);
732 } /* scan iface channel list */
734 return ret
; /* false */
738 See also pim_upstream_evaluate_join_desired() above.
740 void pim_upstream_update_join_desired(struct pim_upstream
*up
)
742 int was_join_desired
; /* boolean */
743 int is_join_desired
; /* boolean */
745 was_join_desired
= PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up
->flags
);
747 is_join_desired
= pim_upstream_evaluate_join_desired(up
);
749 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up
->flags
);
751 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up
->flags
);
753 /* switched from false to true */
754 if (is_join_desired
&& !was_join_desired
) {
755 pim_upstream_switch(up
, PIM_UPSTREAM_JOINED
);
759 /* switched from true to false */
760 if (!is_join_desired
&& was_join_desired
) {
761 pim_upstream_switch(up
, PIM_UPSTREAM_NOTJOINED
);
767 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
768 Transitions from Joined State
769 RPF'(S,G) GenID changes
771 The upstream (S,G) state machine remains in Joined state. If the
772 Join Timer is set to expire in more than t_override seconds, reset
773 it so that it expires after t_override seconds.
775 void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr
)
777 struct listnode
*up_node
;
778 struct listnode
*up_nextnode
;
779 struct pim_upstream
*up
;
782 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
784 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
)) {
786 if (PIM_DEBUG_TRACE
) {
787 char neigh_str
[INET_ADDRSTRLEN
];
788 char rpf_addr_str
[PREFIX_STRLEN
];
789 pim_inet4_dump("<neigh?>", neigh_addr
, neigh_str
, sizeof(neigh_str
));
790 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_addr_str
, sizeof(rpf_addr_str
));
791 zlog_debug("%s: matching neigh=%s against upstream (S,G)=%s joined=%d rpf_addr=%s",
793 neigh_str
, up
->sg_str
,
794 up
->join_state
== PIM_UPSTREAM_JOINED
,
798 /* consider only (S,G) upstream in Joined state */
799 if (up
->join_state
!= PIM_UPSTREAM_JOINED
)
802 /* match RPF'(S,G)=neigh_addr */
803 if (up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
!= neigh_addr
.s_addr
)
806 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
812 void pim_upstream_rpf_interface_changed(struct pim_upstream
*up
,
813 struct interface
*old_rpf_ifp
)
815 struct listnode
*chnode
;
816 struct listnode
*chnextnode
;
817 struct pim_ifchannel
*ch
;
818 struct pim_interface
*pim_ifp
;
820 /* search all ifchannels */
821 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
823 pim_ifp
= ch
->interface
->info
;
827 if (ch
->upstream
!= up
)
830 if (ch
->ifassert_state
== PIM_IFASSERT_I_AM_LOSER
) {
832 /* RPF_interface(S) was NOT I */
833 (old_rpf_ifp
== ch
->interface
)
835 /* RPF_interface(S) stopped being I */
836 (ch
->upstream
->rpf
.source_nexthop
.interface
!= ch
->interface
)
838 assert_action_a5(ch
);
840 } /* PIM_IFASSERT_I_AM_LOSER */
842 pim_ifchannel_update_assert_tracking_desired(ch
);
846 void pim_upstream_update_could_assert(struct pim_upstream
*up
)
848 struct listnode
*chnode
;
849 struct listnode
*chnextnode
;
850 struct pim_interface
*pim_ifp
;
851 struct pim_ifchannel
*ch
;
853 /* scan per-interface (S,G) state */
854 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
855 pim_ifp
= ch
->interface
->info
;
859 if (ch
->upstream
!= up
)
862 pim_ifchannel_update_could_assert(ch
);
863 } /* scan iface channel list */
866 void pim_upstream_update_my_assert_metric(struct pim_upstream
*up
)
868 struct listnode
*chnode
;
869 struct listnode
*chnextnode
;
870 struct pim_interface
*pim_ifp
;
871 struct pim_ifchannel
*ch
;
873 /* scan per-interface (S,G) state */
874 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
875 pim_ifp
= ch
->interface
->info
;
879 if (ch
->upstream
!= up
)
882 pim_ifchannel_update_my_assert_metric(ch
);
884 } /* scan iface channel list */
887 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
)
889 struct listnode
*chnode
;
890 struct listnode
*chnextnode
;
891 struct pim_interface
*pim_ifp
;
892 struct pim_ifchannel
*ch
;
894 /* scan per-interface (S,G) state */
895 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
896 pim_ifp
= ch
->interface
->info
;
900 if (ch
->upstream
!= up
)
903 pim_ifchannel_update_assert_tracking_desired(ch
);
905 } /* scan iface channel list */
908 /* When kat is stopped CouldRegister goes to false so we need to
909 * transition the (S, G) on FHR to NI state and remove reg tunnel
911 static void pim_upstream_fhr_kat_expiry(struct pim_upstream
*up
)
913 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
917 zlog_debug ("kat expired on %s; clear fhr reg state", up
->sg_str
);
919 /* stop reg-stop timer */
920 THREAD_OFF(up
->t_rs_timer
);
921 /* remove regiface from the OIL if it is there*/
922 pim_channel_del_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
923 /* move to "not-joined" */
924 up
->join_state
= PIM_UPSTREAM_NOTJOINED
;
925 PIM_UPSTREAM_FLAG_UNSET_FHR(up
->flags
);
928 /* When kat is started CouldRegister can go to true. And if it does we
929 * need to transition the (S, G) on FHR to JOINED state and add reg tunnel
931 static void pim_upstream_fhr_kat_start(struct pim_upstream
*up
)
933 if (pim_upstream_could_register(up
)) {
935 zlog_debug ("kat started on %s; set fhr reg state to joined", up
->sg_str
);
937 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
938 if (up
->join_state
== PIM_UPSTREAM_NOTJOINED
) {
939 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
940 up
->join_state
= PIM_UPSTREAM_JOINED
;
946 * On an RP, the PMBR value must be cleared when the
947 * Keepalive Timer expires
948 * KAT expiry indicates that flow is inactive. If the flow was created or
949 * maintained by activity now is the time to deref it.
952 pim_upstream_keep_alive_timer (struct thread
*t
)
954 struct pim_upstream
*up
;
957 up
->t_ka_timer
= NULL
;
959 if (I_am_RP (up
->sg
.grp
))
961 pim_br_clear_pmbr (&up
->sg
);
963 * We need to do more here :)
964 * But this is the start.
968 /* source is no longer active - pull the SA from MSDP's cache */
969 pim_msdp_sa_local_del(&up
->sg
);
971 /* if entry was created because of activity we need to deref it */
972 if (PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
974 pim_upstream_fhr_kat_expiry(up
);
976 zlog_debug ("kat expired on %s; remove stream reference", up
->sg_str
);
977 PIM_UPSTREAM_FLAG_UNSET_SRC_STREAM(up
->flags
);
978 pim_upstream_del(up
, __PRETTY_FUNCTION__
);
985 pim_upstream_keep_alive_timer_start (struct pim_upstream
*up
,
988 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
)) {
990 zlog_debug ("kat start on %s with no stream reference", up
->sg_str
);
992 THREAD_OFF (up
->t_ka_timer
);
993 THREAD_TIMER_ON (master
,
995 pim_upstream_keep_alive_timer
,
998 /* any time keepalive is started against a SG we will have to
999 * re-evaluate our active source database */
1000 pim_msdp_sa_local_update(up
);
1003 /* MSDP on RP needs to know if a source is registerable to this RP */
1005 pim_upstream_msdp_reg_timer(struct thread
*t
)
1007 struct pim_upstream
*up
;
1010 up
->t_msdp_reg_timer
= NULL
;
1012 /* source is no longer active - pull the SA from MSDP's cache */
1013 pim_msdp_sa_local_del(&up
->sg
);
1017 pim_upstream_msdp_reg_timer_start(struct pim_upstream
*up
)
1019 THREAD_OFF(up
->t_msdp_reg_timer
);
1020 THREAD_TIMER_ON(master
, up
->t_msdp_reg_timer
,
1021 pim_upstream_msdp_reg_timer
, up
, PIM_MSDP_REG_RXED_PERIOD
);
1023 pim_msdp_sa_local_update(up
);
1027 * 4.2.1 Last-Hop Switchover to the SPT
1029 * In Sparse-Mode PIM, last-hop routers join the shared tree towards the
1030 * RP. Once traffic from sources to joined groups arrives at a last-hop
1031 * router, it has the option of switching to receive the traffic on a
1032 * shortest path tree (SPT).
1034 * The decision for a router to switch to the SPT is controlled as
1038 * CheckSwitchToSpt(S,G) {
1039 * if ( ( pim_include(*,G) (-) pim_exclude(S,G)
1040 * (+) pim_include(S,G) != NULL )
1041 * AND SwitchToSptDesired(S,G) ) {
1042 * # Note: Restarting the KAT will result in the SPT switch
1043 * set KeepaliveTimer(S,G) to Keepalive_Period
1047 * SwitchToSptDesired(S,G) is a policy function that is implementation
1048 * defined. An "infinite threshold" policy can be implemented by making
1049 * SwitchToSptDesired(S,G) return false all the time. A "switch on
1050 * first packet" policy can be implemented by making
1051 * SwitchToSptDesired(S,G) return true once a single packet has been
1052 * received for the source and group.
1055 pim_upstream_switch_to_spt_desired (struct prefix_sg
*sg
)
1057 if (I_am_RP (sg
->grp
))
1064 pim_upstream_is_sg_rpt (struct pim_upstream
*up
)
1066 struct listnode
*chnode
;
1067 struct pim_ifchannel
*ch
;
1069 for (ALL_LIST_ELEMENTS_RO(pim_ifchannel_list
, chnode
, ch
))
1071 if ((ch
->upstream
== up
) &&
1072 (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
)))
1079 * After receiving a packet set SPTbit:
1081 * Update_SPTbit(S,G,iif) {
1082 * if ( iif == RPF_interface(S)
1083 * AND JoinDesired(S,G) == TRUE
1084 * AND ( DirectlyConnected(S) == TRUE
1085 * OR RPF_interface(S) != RPF_interface(RP(G))
1086 * OR inherited_olist(S,G,rpt) == NULL
1087 * OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1088 * ( RPF'(S,G) != NULL ) )
1089 * OR ( I_Am_Assert_Loser(S,G,iif) ) {
1090 * Set SPTbit(S,G) to TRUE
1095 pim_upstream_set_sptbit (struct pim_upstream
*up
, struct interface
*incoming
)
1097 struct pim_rpf
*grpf
= NULL
;
1099 // iif == RPF_interfvace(S)
1100 if (up
->rpf
.source_nexthop
.interface
!= incoming
)
1102 if (PIM_DEBUG_TRACE
)
1103 zlog_debug ("%s: Incoming Interface: %s is different than RPF_interface(S) %s",
1104 __PRETTY_FUNCTION__
, incoming
->name
, up
->rpf
.source_nexthop
.interface
->name
);
1108 // AND JoinDesired(S,G) == TRUE
1111 // DirectlyConnected(S) == TRUE
1112 if (pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
1114 if (PIM_DEBUG_TRACE
)
1115 zlog_debug ("%s: %s is directly connected to the source", __PRETTY_FUNCTION__
,
1117 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1121 // OR RPF_interface(S) != RPF_interface(RP(G))
1122 grpf
= RP(up
->sg
.grp
);
1123 if (!grpf
|| up
->rpf
.source_nexthop
.interface
!= grpf
->source_nexthop
.interface
)
1125 if (PIM_DEBUG_TRACE
)
1126 zlog_debug ("%s: %s RPF_interface(S) != RPF_interface(RP(G))",
1127 __PRETTY_FUNCTION__
, up
->sg_str
);
1128 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1132 // OR inherited_olist(S,G,rpt) == NULL
1133 if (pim_upstream_is_sg_rpt(up
) && pim_upstream_empty_inherited_olist(up
))
1135 if (PIM_DEBUG_TRACE
)
1136 zlog_debug ("%s: %s OR inherited_olist(S,G,rpt) == NULL", __PRETTY_FUNCTION__
,
1138 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1142 // OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1143 // ( RPF'(S,G) != NULL ) )
1144 if (up
->parent
&& pim_rpf_is_same (&up
->rpf
, &up
->parent
->rpf
))
1146 if (PIM_DEBUG_TRACE
)
1147 zlog_debug ("%s: %s RPF'(S,G) is the same as RPF'(*,G)", __PRETTY_FUNCTION__
,
1149 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1157 pim_upstream_state2str (enum pim_upstream_state join_state
)
1161 case PIM_UPSTREAM_NOTJOINED
:
1164 case PIM_UPSTREAM_JOINED
:
1167 case PIM_UPSTREAM_JOIN_PENDING
:
1168 return "JoinPending";
1170 case PIM_UPSTREAM_PRUNE
:
1178 pim_upstream_register_stop_timer (struct thread
*t
)
1180 struct pim_interface
*pim_ifp
;
1181 struct pim_upstream
*up
;
1182 struct pim_rpf
*rpg
;
1184 up
= THREAD_ARG (t
);
1186 up
->t_rs_timer
= NULL
;
1188 if (PIM_DEBUG_TRACE
)
1190 zlog_debug ("%s: (S,G)=%s upstream register stop timer %s",
1191 __PRETTY_FUNCTION__
, up
->sg_str
,
1192 pim_upstream_state2str(up
->join_state
));
1195 switch (up
->join_state
)
1197 case PIM_UPSTREAM_JOIN_PENDING
:
1198 up
->join_state
= PIM_UPSTREAM_JOINED
;
1199 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
1201 case PIM_UPSTREAM_JOINED
:
1203 case PIM_UPSTREAM_PRUNE
:
1204 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1207 if (PIM_DEBUG_TRACE
)
1208 zlog_debug ("%s: Interface: %s is not configured for pim",
1209 __PRETTY_FUNCTION__
, up
->rpf
.source_nexthop
.interface
->name
);
1212 up
->join_state
= PIM_UPSTREAM_JOIN_PENDING
;
1213 pim_upstream_start_register_stop_timer (up
, 1);
1215 if (((up
->channel_oil
->cc
.lastused
/100) > PIM_KEEPALIVE_PERIOD
) &&
1216 (I_am_RP (up
->sg
.grp
)))
1218 if (PIM_DEBUG_TRACE
)
1219 zlog_debug ("%s: Stop sending the register, because I am the RP and we haven't seen a packet in a while", __PRETTY_FUNCTION__
);
1222 rpg
= RP (up
->sg
.grp
);
1223 memset (&ip_hdr
, 0, sizeof (struct ip
));
1224 ip_hdr
.ip_p
= PIM_IP_PROTO_PIM
;
1227 ip_hdr
.ip_src
= up
->sg
.src
;
1228 ip_hdr
.ip_dst
= up
->sg
.grp
;
1229 ip_hdr
.ip_len
= htons (20);
1230 // checksum is broken
1231 pim_register_send ((uint8_t *)&ip_hdr
, sizeof (struct ip
),
1232 pim_ifp
->primary_address
, rpg
, 1, up
);
1242 pim_upstream_start_register_stop_timer (struct pim_upstream
*up
, int null_register
)
1248 THREAD_TIMER_OFF (up
->t_rs_timer
);
1249 up
->t_rs_timer
= NULL
;
1254 uint32_t lower
= (0.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1255 uint32_t upper
= (1.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1256 time
= lower
+ (random () % (upper
- lower
+ 1)) - PIM_REGISTER_PROBE_PERIOD
;
1259 time
= PIM_REGISTER_PROBE_PERIOD
;
1261 if (PIM_DEBUG_TRACE
)
1263 zlog_debug ("%s: (S,G)=%s Starting upstream register stop timer %d",
1264 __PRETTY_FUNCTION__
, up
->sg_str
, time
);
1266 THREAD_TIMER_ON (master
, up
->t_rs_timer
,
1267 pim_upstream_register_stop_timer
,
1272 pim_upstream_inherited_olist_decide (struct pim_upstream
*up
)
1274 struct pim_interface
*pim_ifp
;
1275 struct listnode
*chnextnode
;
1276 struct pim_ifchannel
*ch
;
1277 struct listnode
*chnode
;
1278 int output_intf
= 0;
1280 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1281 if (pim_ifp
&& !up
->channel_oil
)
1282 up
->channel_oil
= pim_channel_oil_add (&up
->sg
, pim_ifp
->mroute_vif_index
);
1284 for (ALL_LIST_ELEMENTS (pim_ifchannel_list
, chnode
, chnextnode
, ch
))
1286 pim_ifp
= ch
->interface
->info
;
1290 if (pim_upstream_evaluate_join_desired_interface (up
, ch
))
1292 pim_channel_add_oif (up
->channel_oil
, ch
->interface
, PIM_OIF_FLAG_PROTO_PIM
);
1301 * For a given upstream, determine the inherited_olist
1304 * inherited_olist(S,G,rpt) =
1305 * ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
1306 * (+) ( pim_include(*,G) (-) pim_exclude(S,G))
1307 * (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) )
1309 * inherited_olist(S,G) =
1310 * inherited_olist(S,G,rpt) (+)
1311 * joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
1313 * return 1 if there are any output interfaces
1314 * return 0 if there are not any output interfaces
1317 pim_upstream_inherited_olist (struct pim_upstream
*up
)
1319 int output_intf
= pim_upstream_inherited_olist_decide (up
);
1322 * If we have output_intf switch state to Join and work like normal
1323 * If we don't have an output_intf that means we are probably a
1324 * switch on a stick so turn on forwarding to just accept the
1325 * incoming packets so we don't bother the other stuff!
1328 pim_upstream_switch (up
, PIM_UPSTREAM_JOINED
);
1336 pim_upstream_empty_inherited_olist (struct pim_upstream
*up
)
1338 return pim_channel_oil_empty (up
->channel_oil
);
1342 * When we have a new neighbor,
1343 * find upstreams that don't have their rpf_addr
1344 * set and see if the new neighbor allows
1345 * the join to be sent
1348 pim_upstream_find_new_rpf (void)
1350 struct listnode
*up_node
;
1351 struct listnode
*up_nextnode
;
1352 struct pim_upstream
*up
;
1355 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
1357 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
))
1359 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
))
1361 if (PIM_DEBUG_TRACE
)
1362 zlog_debug ("Upstream %s without a path to send join, checking",
1364 pim_rpf_update (up
, NULL
);
1370 pim_upstream_hash_key (void *arg
)
1372 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1374 return jhash_2words (up
->sg
.src
.s_addr
, up
->sg
.grp
.s_addr
, 0);
1377 void pim_upstream_terminate (void)
1379 if (pim_upstream_list
)
1380 list_free (pim_upstream_list
);
1381 pim_upstream_list
= NULL
;
1383 if (pim_upstream_hash
)
1384 hash_free (pim_upstream_hash
);
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
;