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
);
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
*pim_upstream_new(struct prefix_sg
*sg
,
523 struct interface
*incoming
,
526 struct pim_upstream
*up
;
527 enum pim_rpf_result rpf_result
;
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 listnode_add_sort(pim_upstream_list
, up
);
608 zlog_debug ("%s: Created Upstream %s", __PRETTY_FUNCTION__
, up
->sg_str
);
613 struct pim_upstream
*pim_upstream_find(struct prefix_sg
*sg
)
615 struct pim_upstream lookup
;
616 struct pim_upstream
*up
= NULL
;
619 up
= hash_lookup (pim_upstream_hash
, &lookup
);
623 static void pim_upstream_ref(struct pim_upstream
*up
, int flags
)
629 struct pim_upstream
*pim_upstream_add(struct prefix_sg
*sg
,
630 struct interface
*incoming
,
631 int flags
, const char *name
)
633 struct pim_upstream
*up
= NULL
;
635 up
= pim_upstream_find(sg
);
637 pim_upstream_ref(up
, flags
);
641 up
= pim_upstream_new(sg
, incoming
, flags
);
647 zlog_debug("%s(%s): %s, found: %d: ref_count: %d",
648 __PRETTY_FUNCTION__
, name
,
652 zlog_debug("%s(%s): (%s) failure to create",
653 __PRETTY_FUNCTION__
, name
,
654 pim_str_sg_dump (sg
));
661 pim_upstream_evaluate_join_desired_interface (struct pim_upstream
*up
,
662 struct pim_ifchannel
*ch
)
664 struct pim_upstream
*parent
= up
->parent
;
666 if (ch
->upstream
== up
)
668 if (!pim_macro_ch_lost_assert(ch
) && pim_macro_chisin_joins_or_include(ch
))
671 if (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
))
678 if (parent
&& ch
->upstream
== parent
)
680 if (!pim_macro_ch_lost_assert (ch
) && pim_macro_chisin_joins_or_include (ch
))
688 Evaluate JoinDesired(S,G):
690 JoinDesired(S,G) is true if there is a downstream (S,G) interface I
693 inherited_olist(S,G) =
694 joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
696 JoinDesired(S,G) may be affected by changes in the following:
698 pim_ifp->primary_address
700 ch->ifassert_winner_metric
702 ch->local_ifmembership
704 ch->upstream->rpf.source_nexthop.mrib_metric_preference
705 ch->upstream->rpf.source_nexthop.mrib_route_metric
706 ch->upstream->rpf.source_nexthop.interface
708 See also pim_upstream_update_join_desired() below.
710 int pim_upstream_evaluate_join_desired(struct pim_upstream
*up
)
712 struct listnode
*chnode
;
713 struct listnode
*chnextnode
;
714 struct pim_interface
*pim_ifp
;
715 struct pim_ifchannel
*ch
;
718 /* scan per-interface (S,G) state */
719 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
))
721 pim_ifp
= ch
->interface
->info
;
725 ret
+= pim_upstream_evaluate_join_desired_interface (up
, ch
);
726 } /* scan iface channel list */
728 return ret
; /* false */
732 See also pim_upstream_evaluate_join_desired() above.
734 void pim_upstream_update_join_desired(struct pim_upstream
*up
)
736 int was_join_desired
; /* boolean */
737 int is_join_desired
; /* boolean */
739 was_join_desired
= PIM_UPSTREAM_FLAG_TEST_DR_JOIN_DESIRED(up
->flags
);
741 is_join_desired
= pim_upstream_evaluate_join_desired(up
);
743 PIM_UPSTREAM_FLAG_SET_DR_JOIN_DESIRED(up
->flags
);
745 PIM_UPSTREAM_FLAG_UNSET_DR_JOIN_DESIRED(up
->flags
);
747 /* switched from false to true */
748 if (is_join_desired
&& !was_join_desired
) {
749 pim_upstream_switch(up
, PIM_UPSTREAM_JOINED
);
753 /* switched from true to false */
754 if (!is_join_desired
&& was_join_desired
) {
755 pim_upstream_switch(up
, PIM_UPSTREAM_NOTJOINED
);
761 RFC 4601 4.5.7. Sending (S,G) Join/Prune Messages
762 Transitions from Joined State
763 RPF'(S,G) GenID changes
765 The upstream (S,G) state machine remains in Joined state. If the
766 Join Timer is set to expire in more than t_override seconds, reset
767 it so that it expires after t_override seconds.
769 void pim_upstream_rpf_genid_changed(struct in_addr neigh_addr
)
771 struct listnode
*up_node
;
772 struct listnode
*up_nextnode
;
773 struct pim_upstream
*up
;
776 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
778 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
)) {
780 if (PIM_DEBUG_TRACE
) {
781 char neigh_str
[INET_ADDRSTRLEN
];
782 char rpf_addr_str
[PREFIX_STRLEN
];
783 pim_inet4_dump("<neigh?>", neigh_addr
, neigh_str
, sizeof(neigh_str
));
784 pim_addr_dump("<rpf?>", &up
->rpf
.rpf_addr
, rpf_addr_str
, sizeof(rpf_addr_str
));
785 zlog_debug("%s: matching neigh=%s against upstream (S,G)=%s joined=%d rpf_addr=%s",
787 neigh_str
, up
->sg_str
,
788 up
->join_state
== PIM_UPSTREAM_JOINED
,
792 /* consider only (S,G) upstream in Joined state */
793 if (up
->join_state
!= PIM_UPSTREAM_JOINED
)
796 /* match RPF'(S,G)=neigh_addr */
797 if (up
->rpf
.rpf_addr
.u
.prefix4
.s_addr
!= neigh_addr
.s_addr
)
800 pim_upstream_join_timer_decrease_to_t_override("RPF'(S,G) GenID change",
806 void pim_upstream_rpf_interface_changed(struct pim_upstream
*up
,
807 struct interface
*old_rpf_ifp
)
809 struct listnode
*chnode
;
810 struct listnode
*chnextnode
;
811 struct pim_ifchannel
*ch
;
812 struct pim_interface
*pim_ifp
;
814 /* search all ifchannels */
815 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
817 pim_ifp
= ch
->interface
->info
;
821 if (ch
->upstream
!= up
)
824 if (ch
->ifassert_state
== PIM_IFASSERT_I_AM_LOSER
) {
826 /* RPF_interface(S) was NOT I */
827 (old_rpf_ifp
== ch
->interface
)
829 /* RPF_interface(S) stopped being I */
830 (ch
->upstream
->rpf
.source_nexthop
.interface
!= ch
->interface
)
832 assert_action_a5(ch
);
834 } /* PIM_IFASSERT_I_AM_LOSER */
836 pim_ifchannel_update_assert_tracking_desired(ch
);
840 void pim_upstream_update_could_assert(struct pim_upstream
*up
)
842 struct listnode
*chnode
;
843 struct listnode
*chnextnode
;
844 struct pim_interface
*pim_ifp
;
845 struct pim_ifchannel
*ch
;
847 /* scan per-interface (S,G) state */
848 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
849 pim_ifp
= ch
->interface
->info
;
853 if (ch
->upstream
!= up
)
856 pim_ifchannel_update_could_assert(ch
);
857 } /* scan iface channel list */
860 void pim_upstream_update_my_assert_metric(struct pim_upstream
*up
)
862 struct listnode
*chnode
;
863 struct listnode
*chnextnode
;
864 struct pim_interface
*pim_ifp
;
865 struct pim_ifchannel
*ch
;
867 /* scan per-interface (S,G) state */
868 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
869 pim_ifp
= ch
->interface
->info
;
873 if (ch
->upstream
!= up
)
876 pim_ifchannel_update_my_assert_metric(ch
);
878 } /* scan iface channel list */
881 static void pim_upstream_update_assert_tracking_desired(struct pim_upstream
*up
)
883 struct listnode
*chnode
;
884 struct listnode
*chnextnode
;
885 struct pim_interface
*pim_ifp
;
886 struct pim_ifchannel
*ch
;
888 /* scan per-interface (S,G) state */
889 for (ALL_LIST_ELEMENTS(pim_ifchannel_list
, chnode
, chnextnode
, ch
)) {
890 pim_ifp
= ch
->interface
->info
;
894 if (ch
->upstream
!= up
)
897 pim_ifchannel_update_assert_tracking_desired(ch
);
899 } /* scan iface channel list */
902 /* When kat is stopped CouldRegister goes to false so we need to
903 * transition the (S, G) on FHR to NI state and remove reg tunnel
905 static void pim_upstream_fhr_kat_expiry(struct pim_upstream
*up
)
907 if (!PIM_UPSTREAM_FLAG_TEST_FHR(up
->flags
))
911 zlog_debug ("kat expired on %s; clear fhr reg state", up
->sg_str
);
913 /* stop reg-stop timer */
914 THREAD_OFF(up
->t_rs_timer
);
915 /* remove regiface from the OIL if it is there*/
916 pim_channel_del_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
917 /* move to "not-joined" */
918 up
->join_state
= PIM_UPSTREAM_NOTJOINED
;
919 PIM_UPSTREAM_FLAG_UNSET_FHR(up
->flags
);
922 /* When kat is started CouldRegister can go to true. And if it does we
923 * need to transition the (S, G) on FHR to JOINED state and add reg tunnel
925 static void pim_upstream_fhr_kat_start(struct pim_upstream
*up
)
927 if (pim_upstream_could_register(up
)) {
929 zlog_debug ("kat started on %s; set fhr reg state to joined", up
->sg_str
);
931 PIM_UPSTREAM_FLAG_SET_FHR(up
->flags
);
932 if (up
->join_state
== PIM_UPSTREAM_NOTJOINED
) {
933 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
934 up
->join_state
= PIM_UPSTREAM_JOINED
;
940 * On an RP, the PMBR value must be cleared when the
941 * Keepalive Timer expires
942 * KAT expiry indicates that flow is inactive. If the flow was created or
943 * maintained by activity now is the time to deref it.
946 pim_upstream_keep_alive_timer (struct thread
*t
)
948 struct pim_upstream
*up
;
951 up
->t_ka_timer
= NULL
;
953 if (I_am_RP (up
->sg
.grp
))
955 pim_br_clear_pmbr (&up
->sg
);
957 * We need to do more here :)
958 * But this is the start.
962 /* source is no longer active - pull the SA from MSDP's cache */
963 pim_msdp_sa_local_del(&up
->sg
);
965 /* if entry was created because of activity we need to deref it */
966 if (PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
968 pim_upstream_fhr_kat_expiry(up
);
970 zlog_debug ("kat expired on %s; remove stream reference", up
->sg_str
);
971 PIM_UPSTREAM_FLAG_UNSET_SRC_STREAM(up
->flags
);
972 pim_upstream_del(up
, __PRETTY_FUNCTION__
);
979 pim_upstream_keep_alive_timer_start (struct pim_upstream
*up
,
982 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
)) {
984 zlog_debug ("kat start on %s with no stream reference", up
->sg_str
);
986 THREAD_OFF (up
->t_ka_timer
);
987 THREAD_TIMER_ON (master
,
989 pim_upstream_keep_alive_timer
,
992 /* any time keepalive is started against a SG we will have to
993 * re-evaluate our active source database */
994 pim_msdp_sa_local_update(up
);
997 /* MSDP on RP needs to know if a source is registerable to this RP */
999 pim_upstream_msdp_reg_timer(struct thread
*t
)
1001 struct pim_upstream
*up
;
1004 up
->t_msdp_reg_timer
= NULL
;
1006 /* source is no longer active - pull the SA from MSDP's cache */
1007 pim_msdp_sa_local_del(&up
->sg
);
1011 pim_upstream_msdp_reg_timer_start(struct pim_upstream
*up
)
1013 THREAD_OFF(up
->t_msdp_reg_timer
);
1014 THREAD_TIMER_ON(master
, up
->t_msdp_reg_timer
,
1015 pim_upstream_msdp_reg_timer
, up
, PIM_MSDP_REG_RXED_PERIOD
);
1017 pim_msdp_sa_local_update(up
);
1021 * 4.2.1 Last-Hop Switchover to the SPT
1023 * In Sparse-Mode PIM, last-hop routers join the shared tree towards the
1024 * RP. Once traffic from sources to joined groups arrives at a last-hop
1025 * router, it has the option of switching to receive the traffic on a
1026 * shortest path tree (SPT).
1028 * The decision for a router to switch to the SPT is controlled as
1032 * CheckSwitchToSpt(S,G) {
1033 * if ( ( pim_include(*,G) (-) pim_exclude(S,G)
1034 * (+) pim_include(S,G) != NULL )
1035 * AND SwitchToSptDesired(S,G) ) {
1036 * # Note: Restarting the KAT will result in the SPT switch
1037 * set KeepaliveTimer(S,G) to Keepalive_Period
1041 * SwitchToSptDesired(S,G) is a policy function that is implementation
1042 * defined. An "infinite threshold" policy can be implemented by making
1043 * SwitchToSptDesired(S,G) return false all the time. A "switch on
1044 * first packet" policy can be implemented by making
1045 * SwitchToSptDesired(S,G) return true once a single packet has been
1046 * received for the source and group.
1049 pim_upstream_switch_to_spt_desired (struct prefix_sg
*sg
)
1051 if (I_am_RP (sg
->grp
))
1058 pim_upstream_is_sg_rpt (struct pim_upstream
*up
)
1060 struct listnode
*chnode
;
1061 struct pim_ifchannel
*ch
;
1063 for (ALL_LIST_ELEMENTS_RO(pim_ifchannel_list
, chnode
, ch
))
1065 if ((ch
->upstream
== up
) &&
1066 (PIM_IF_FLAG_TEST_S_G_RPT(ch
->flags
)))
1073 * After receiving a packet set SPTbit:
1075 * Update_SPTbit(S,G,iif) {
1076 * if ( iif == RPF_interface(S)
1077 * AND JoinDesired(S,G) == TRUE
1078 * AND ( DirectlyConnected(S) == TRUE
1079 * OR RPF_interface(S) != RPF_interface(RP(G))
1080 * OR inherited_olist(S,G,rpt) == NULL
1081 * OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1082 * ( RPF'(S,G) != NULL ) )
1083 * OR ( I_Am_Assert_Loser(S,G,iif) ) {
1084 * Set SPTbit(S,G) to TRUE
1089 pim_upstream_set_sptbit (struct pim_upstream
*up
, struct interface
*incoming
)
1091 struct pim_rpf
*grpf
= NULL
;
1093 // iif == RPF_interfvace(S)
1094 if (up
->rpf
.source_nexthop
.interface
!= incoming
)
1096 if (PIM_DEBUG_TRACE
)
1097 zlog_debug ("%s: Incoming Interface: %s is different than RPF_interface(S) %s",
1098 __PRETTY_FUNCTION__
, incoming
->name
, up
->rpf
.source_nexthop
.interface
->name
);
1102 // AND JoinDesired(S,G) == TRUE
1105 // DirectlyConnected(S) == TRUE
1106 if (pim_if_connected_to_source (up
->rpf
.source_nexthop
.interface
, up
->sg
.src
))
1108 if (PIM_DEBUG_TRACE
)
1109 zlog_debug ("%s: %s is directly connected to the source", __PRETTY_FUNCTION__
,
1111 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1115 // OR RPF_interface(S) != RPF_interface(RP(G))
1116 grpf
= RP(up
->sg
.grp
);
1117 if (!grpf
|| up
->rpf
.source_nexthop
.interface
!= grpf
->source_nexthop
.interface
)
1119 if (PIM_DEBUG_TRACE
)
1120 zlog_debug ("%s: %s RPF_interface(S) != RPF_interface(RP(G))",
1121 __PRETTY_FUNCTION__
, up
->sg_str
);
1122 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1126 // OR inherited_olist(S,G,rpt) == NULL
1127 if (pim_upstream_is_sg_rpt(up
) && pim_upstream_empty_inherited_olist(up
))
1129 if (PIM_DEBUG_TRACE
)
1130 zlog_debug ("%s: %s OR inherited_olist(S,G,rpt) == NULL", __PRETTY_FUNCTION__
,
1132 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1136 // OR ( ( RPF'(S,G) == RPF'(*,G) ) AND
1137 // ( RPF'(S,G) != NULL ) )
1138 if (up
->parent
&& pim_rpf_is_same (&up
->rpf
, &up
->parent
->rpf
))
1140 if (PIM_DEBUG_TRACE
)
1141 zlog_debug ("%s: %s RPF'(S,G) is the same as RPF'(*,G)", __PRETTY_FUNCTION__
,
1143 up
->sptbit
= PIM_UPSTREAM_SPTBIT_TRUE
;
1151 pim_upstream_state2str (enum pim_upstream_state join_state
)
1155 case PIM_UPSTREAM_NOTJOINED
:
1158 case PIM_UPSTREAM_JOINED
:
1161 case PIM_UPSTREAM_JOIN_PENDING
:
1162 return "JoinPending";
1164 case PIM_UPSTREAM_PRUNE
:
1172 pim_upstream_register_stop_timer (struct thread
*t
)
1174 struct pim_interface
*pim_ifp
;
1175 struct pim_upstream
*up
;
1176 struct pim_rpf
*rpg
;
1178 up
= THREAD_ARG (t
);
1180 up
->t_rs_timer
= NULL
;
1182 if (PIM_DEBUG_TRACE
)
1184 zlog_debug ("%s: (S,G)=%s upstream register stop timer %s",
1185 __PRETTY_FUNCTION__
, up
->sg_str
,
1186 pim_upstream_state2str(up
->join_state
));
1189 switch (up
->join_state
)
1191 case PIM_UPSTREAM_JOIN_PENDING
:
1192 up
->join_state
= PIM_UPSTREAM_JOINED
;
1193 pim_channel_add_oif (up
->channel_oil
, pim_regiface
, PIM_OIF_FLAG_PROTO_PIM
);
1195 case PIM_UPSTREAM_JOINED
:
1197 case PIM_UPSTREAM_PRUNE
:
1198 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1201 if (PIM_DEBUG_TRACE
)
1202 zlog_debug ("%s: Interface: %s is not configured for pim",
1203 __PRETTY_FUNCTION__
, up
->rpf
.source_nexthop
.interface
->name
);
1206 up
->join_state
= PIM_UPSTREAM_JOIN_PENDING
;
1207 pim_upstream_start_register_stop_timer (up
, 1);
1209 if (((up
->channel_oil
->cc
.lastused
/100) > PIM_KEEPALIVE_PERIOD
) &&
1210 (I_am_RP (up
->sg
.grp
)))
1212 if (PIM_DEBUG_TRACE
)
1213 zlog_debug ("%s: Stop sending the register, because I am the RP and we haven't seen a packet in a while", __PRETTY_FUNCTION__
);
1216 rpg
= RP (up
->sg
.grp
);
1217 memset (&ip_hdr
, 0, sizeof (struct ip
));
1218 ip_hdr
.ip_p
= PIM_IP_PROTO_PIM
;
1221 ip_hdr
.ip_src
= up
->sg
.src
;
1222 ip_hdr
.ip_dst
= up
->sg
.grp
;
1223 ip_hdr
.ip_len
= htons (20);
1224 // checksum is broken
1225 pim_register_send ((uint8_t *)&ip_hdr
, sizeof (struct ip
),
1226 pim_ifp
->primary_address
, rpg
, 1, up
);
1236 pim_upstream_start_register_stop_timer (struct pim_upstream
*up
, int null_register
)
1242 THREAD_TIMER_OFF (up
->t_rs_timer
);
1243 up
->t_rs_timer
= NULL
;
1248 uint32_t lower
= (0.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1249 uint32_t upper
= (1.5 * PIM_REGISTER_SUPPRESSION_PERIOD
);
1250 time
= lower
+ (random () % (upper
- lower
+ 1)) - PIM_REGISTER_PROBE_PERIOD
;
1253 time
= PIM_REGISTER_PROBE_PERIOD
;
1255 if (PIM_DEBUG_TRACE
)
1257 zlog_debug ("%s: (S,G)=%s Starting upstream register stop timer %d",
1258 __PRETTY_FUNCTION__
, up
->sg_str
, time
);
1260 THREAD_TIMER_ON (master
, up
->t_rs_timer
,
1261 pim_upstream_register_stop_timer
,
1266 * For a given upstream, determine the inherited_olist
1269 * inherited_olist(S,G,rpt) =
1270 * ( joins(*,*,RP(G)) (+) joins(*,G) (-) prunes(S,G,rpt) )
1271 * (+) ( pim_include(*,G) (-) pim_exclude(S,G))
1272 * (-) ( lost_assert(*,G) (+) lost_assert(S,G,rpt) )
1274 * inherited_olist(S,G) =
1275 * inherited_olist(S,G,rpt) (+)
1276 * joins(S,G) (+) pim_include(S,G) (-) lost_assert(S,G)
1278 * return 1 if there are any output interfaces
1279 * return 0 if there are not any output interfaces
1282 pim_upstream_inherited_olist (struct pim_upstream
*up
)
1284 struct pim_interface
*pim_ifp
;
1285 struct listnode
*chnextnode
;
1286 struct pim_ifchannel
*ch
;
1287 struct listnode
*chnode
;
1288 int output_intf
= 0;
1290 pim_ifp
= up
->rpf
.source_nexthop
.interface
->info
;
1291 if (pim_ifp
&& !up
->channel_oil
)
1292 up
->channel_oil
= pim_channel_oil_add (&up
->sg
, pim_ifp
->mroute_vif_index
);
1294 for (ALL_LIST_ELEMENTS (pim_ifchannel_list
, chnode
, chnextnode
, ch
))
1296 pim_ifp
= ch
->interface
->info
;
1300 if (pim_upstream_evaluate_join_desired_interface (up
, ch
))
1302 pim_channel_add_oif (up
->channel_oil
, ch
->interface
, PIM_OIF_FLAG_PROTO_PIM
);
1308 * If we have output_intf switch state to Join and work like normal
1309 * If we don't have an output_intf that means we are probably a
1310 * switch on a stick so turn on forwarding to just accept the
1311 * incoming packets so we don't bother the other stuff!
1314 pim_upstream_switch (up
, PIM_UPSTREAM_JOINED
);
1322 pim_upstream_empty_inherited_olist (struct pim_upstream
*up
)
1324 return pim_channel_oil_empty (up
->channel_oil
);
1328 * When we have a new neighbor,
1329 * find upstreams that don't have their rpf_addr
1330 * set and see if the new neighbor allows
1331 * the join to be sent
1334 pim_upstream_find_new_rpf (void)
1336 struct listnode
*up_node
;
1337 struct listnode
*up_nextnode
;
1338 struct pim_upstream
*up
;
1341 * Scan all (S,G) upstreams searching for RPF'(S,G)=neigh_addr
1343 for (ALL_LIST_ELEMENTS(pim_upstream_list
, up_node
, up_nextnode
, up
))
1345 if (pim_rpf_addr_is_inaddr_any(&up
->rpf
))
1347 if (PIM_DEBUG_TRACE
)
1348 zlog_debug ("Upstream %s without a path to send join, checking",
1350 pim_rpf_update (up
, NULL
);
1356 pim_upstream_hash_key (void *arg
)
1358 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1360 return jhash_2words (up
->sg
.src
.s_addr
, up
->sg
.grp
.s_addr
, 0);
1363 void pim_upstream_terminate (void)
1365 if (pim_upstream_list
)
1366 list_free (pim_upstream_list
);
1367 pim_upstream_list
= NULL
;
1369 if (pim_upstream_hash
)
1370 hash_free (pim_upstream_hash
);
1374 pim_upstream_equal (const void *arg1
, const void *arg2
)
1376 const struct pim_upstream
*up1
= (const struct pim_upstream
*)arg1
;
1377 const struct pim_upstream
*up2
= (const struct pim_upstream
*)arg2
;
1379 if ((up1
->sg
.grp
.s_addr
== up2
->sg
.grp
.s_addr
) &&
1380 (up1
->sg
.src
.s_addr
== up2
->sg
.src
.s_addr
))
1386 /* rfc4601:section-4.2:"Data Packet Forwarding Rules" defines
1387 * the cases where kat has to be restarted on rxing traffic -
1389 * if( DirectlyConnected(S) == TRUE AND iif == RPF_interface(S) ) {
1390 * set KeepaliveTimer(S,G) to Keepalive_Period
1391 * # Note: a register state transition or UpstreamJPState(S,G)
1392 * # transition may happen as a result of restarting
1393 * # KeepaliveTimer, and must be dealt with here.
1395 * if( iif == RPF_interface(S) AND UpstreamJPState(S,G) == Joined AND
1396 * inherited_olist(S,G) != NULL ) {
1397 * set KeepaliveTimer(S,G) to Keepalive_Period
1400 static bool pim_upstream_kat_start_ok(struct pim_upstream
*up
)
1402 /* "iif == RPF_interface(S)" check has to be done by the kernel or hw
1403 * so we will skip that here */
1404 if (pim_if_connected_to_source(up
->rpf
.source_nexthop
.interface
,
1409 if ((up
->join_state
== PIM_UPSTREAM_JOINED
) &&
1410 !pim_upstream_empty_inherited_olist(up
)) {
1411 /* XXX: I have added this RP check just for 3.2 and it's a digression from
1412 * what rfc-4601 says. Till now we were only running KAT on FHR and RP and
1413 * there is some angst around making the change to run it all routers that
1414 * maintain the (S, G) state. This is tracked via CM-13601 and MUST be
1415 * removed to handle spt turn-arounds correctly in a 3-tier clos */
1416 if (I_am_RP (up
->sg
.grp
))
1424 * Code to check and see if we've received packets on a S,G mroute
1425 * and if so to set the SPT bit appropriately
1428 pim_upstream_sg_running (void *arg
)
1430 struct pim_upstream
*up
= (struct pim_upstream
*)arg
;
1432 // No packet can have arrived here if this is the case
1433 if (!up
->channel_oil
|| !up
->channel_oil
->installed
)
1435 if (PIM_DEBUG_TRACE
)
1436 zlog_debug ("%s: %s is not installed in mroute",
1437 __PRETTY_FUNCTION__
, up
->sg_str
);
1442 pim_mroute_update_counters (up
->channel_oil
);
1444 // Have we seen packets?
1445 if ((up
->channel_oil
->cc
.oldpktcnt
>= up
->channel_oil
->cc
.pktcnt
) &&
1446 (up
->channel_oil
->cc
.lastused
/100 > 30))
1448 if (PIM_DEBUG_TRACE
)
1450 zlog_debug ("%s: %s old packet count is equal or lastused is greater than 30, (%ld,%ld,%lld)",
1451 __PRETTY_FUNCTION__
, up
->sg_str
,
1452 up
->channel_oil
->cc
.oldpktcnt
,
1453 up
->channel_oil
->cc
.pktcnt
,
1454 up
->channel_oil
->cc
.lastused
/100);
1459 if (pim_upstream_kat_start_ok(up
)) {
1460 /* Add a source reference to the stream if
1461 * one doesn't already exist */
1462 if (!PIM_UPSTREAM_FLAG_TEST_SRC_STREAM(up
->flags
))
1464 if (PIM_DEBUG_TRACE
)
1465 zlog_debug ("source reference created on kat restart %s", up
->sg_str
);
1467 pim_upstream_ref(up
, PIM_UPSTREAM_FLAG_MASK_SRC_STREAM
);
1468 PIM_UPSTREAM_FLAG_SET_SRC_STREAM(up
->flags
);
1469 pim_upstream_fhr_kat_start(up
);
1471 pim_upstream_keep_alive_timer_start(up
, qpim_keep_alive_time
);
1474 if (up
->sptbit
!= PIM_UPSTREAM_SPTBIT_TRUE
)
1476 pim_upstream_set_sptbit(up
, up
->rpf
.source_nexthop
.interface
);
1482 pim_upstream_init (void)
1484 pim_upstream_sg_wheel
= wheel_init (master
, 31000, 100,
1485 pim_upstream_hash_key
,
1486 pim_upstream_sg_running
);
1487 pim_upstream_hash
= hash_create_size (8192, pim_upstream_hash_key
,
1488 pim_upstream_equal
);
1490 pim_upstream_list
= list_new ();
1491 pim_upstream_list
->del
= (void (*)(void *)) pim_upstream_free
;
1492 pim_upstream_list
->cmp
= pim_upstream_compare
;