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,
31 #include "pim_neighbor.h"
34 #include "pim_iface.h"
36 #include "pim_upstream.h"
37 #include "pim_ifchannel.h"
39 #include "pim_zebra.h"
41 static void dr_election_by_addr(struct interface
*ifp
)
43 struct pim_interface
*pim_ifp
;
44 struct listnode
*node
;
45 struct pim_neighbor
*neigh
;
50 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
52 if (PIM_DEBUG_PIM_TRACE
) {
53 zlog_debug("%s: on interface %s",
58 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
59 if (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
)) {
60 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
65 static void dr_election_by_pri(struct interface
*ifp
)
67 struct pim_interface
*pim_ifp
;
68 struct listnode
*node
;
69 struct pim_neighbor
*neigh
;
75 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
76 dr_pri
= pim_ifp
->pim_dr_priority
;
78 if (PIM_DEBUG_PIM_TRACE
) {
79 zlog_debug("%s: dr pri %u on interface %s",
84 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
85 if (PIM_DEBUG_PIM_TRACE
) {
86 zlog_info("%s: neigh pri %u addr %x if dr addr %x",
89 ntohl(neigh
->source_addr
.s_addr
),
90 ntohl(pim_ifp
->pim_dr_addr
.s_addr
));
93 (neigh
->dr_priority
> dr_pri
) ||
95 (neigh
->dr_priority
== dr_pri
) &&
96 (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
))
99 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
100 dr_pri
= neigh
->dr_priority
;
106 RFC 4601: 4.3.2. DR Election
108 A router's idea of the current DR on an interface can change when a
109 PIM Hello message is received, when a neighbor times out, or when a
110 router's own DR Priority changes.
112 int pim_if_dr_election(struct interface
*ifp
)
114 struct pim_interface
*pim_ifp
= ifp
->info
;
115 struct in_addr old_dr_addr
;
117 ++pim_ifp
->pim_dr_election_count
;
119 old_dr_addr
= pim_ifp
->pim_dr_addr
;
121 if (pim_ifp
->pim_dr_num_nondrpri_neighbors
) {
122 dr_election_by_addr(ifp
);
125 dr_election_by_pri(ifp
);
129 if (old_dr_addr
.s_addr
!= pim_ifp
->pim_dr_addr
.s_addr
) {
131 if (PIM_DEBUG_PIM_EVENTS
) {
132 char dr_old_str
[INET_ADDRSTRLEN
];
133 char dr_new_str
[INET_ADDRSTRLEN
];
134 pim_inet4_dump("<old_dr?>", old_dr_addr
, dr_old_str
, sizeof(dr_old_str
));
135 pim_inet4_dump("<new_dr?>", pim_ifp
->pim_dr_addr
, dr_new_str
, sizeof(dr_new_str
));
136 zlog_debug("%s: DR was %s now is %s on interface %s",
138 dr_old_str
, dr_new_str
, ifp
->name
);
141 pim_ifp
->pim_dr_election_last
= pim_time_monotonic_sec(); /* timestamp */
142 ++pim_ifp
->pim_dr_election_changes
;
143 pim_if_update_join_desired(pim_ifp
);
144 pim_if_update_could_assert(ifp
);
145 pim_if_update_assert_tracking_desired(ifp
);
152 static void update_dr_priority(struct pim_neighbor
*neigh
,
153 pim_hello_options hello_options
,
154 uint32_t dr_priority
)
156 pim_hello_options will_set_pri
; /* boolean */
157 pim_hello_options bit_flip
; /* boolean */
158 pim_hello_options pri_change
; /* boolean */
160 will_set_pri
= PIM_OPTION_IS_SET(hello_options
,
161 PIM_OPTION_MASK_DR_PRIORITY
);
166 PIM_OPTION_IS_SET(neigh
->hello_options
, PIM_OPTION_MASK_DR_PRIORITY
)
170 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
172 /* update num. of neighbors without dr_pri */
175 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
178 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
186 (neigh
->dr_priority
!= dr_priority
)
190 neigh
->dr_priority
= dr_priority
;
193 neigh
->dr_priority
= 0; /* cosmetic unset */
198 RFC 4601: 4.3.2. DR Election
200 A router's idea of the current DR on an interface can change when a
201 PIM Hello message is received, when a neighbor times out, or when a
202 router's own DR Priority changes.
204 pim_if_dr_election(neigh
->interface
); // router's own DR Priority changes
208 static int on_neighbor_timer(struct thread
*t
)
210 struct pim_neighbor
*neigh
;
211 struct interface
*ifp
;
214 neigh
= THREAD_ARG(t
);
216 ifp
= neigh
->interface
;
218 if (PIM_DEBUG_PIM_TRACE
) {
219 char src_str
[INET_ADDRSTRLEN
];
220 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
221 zlog_debug("Expired %d sec holdtime for neighbor %s on interface %s",
222 neigh
->holdtime
, src_str
, ifp
->name
);
225 neigh
->t_expire_timer
= NULL
;
227 snprintf(msg
, sizeof(msg
), "%d-sec holdtime expired", neigh
->holdtime
);
228 pim_neighbor_delete(ifp
, neigh
, msg
);
231 RFC 4601: 4.3.2. DR Election
233 A router's idea of the current DR on an interface can change when a
234 PIM Hello message is received, when a neighbor times out, or when a
235 router's own DR Priority changes.
237 pim_if_dr_election(ifp
); // neighbor times out
242 void pim_neighbor_timer_reset(struct pim_neighbor
*neigh
, uint16_t holdtime
)
244 neigh
->holdtime
= holdtime
;
246 THREAD_OFF(neigh
->t_expire_timer
);
249 0xFFFF is request for no holdtime
251 if (neigh
->holdtime
== 0xFFFF) {
255 if (PIM_DEBUG_PIM_TRACE_DETAIL
) {
256 char src_str
[INET_ADDRSTRLEN
];
257 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
258 zlog_debug("%s: starting %u sec timer for neighbor %s on %s",
260 neigh
->holdtime
, src_str
, neigh
->interface
->name
);
263 THREAD_TIMER_ON(master
, neigh
->t_expire_timer
,
265 neigh
, neigh
->holdtime
);
268 static struct pim_neighbor
*pim_neighbor_new(struct interface
*ifp
,
269 struct in_addr source_addr
,
270 pim_hello_options hello_options
,
272 uint16_t propagation_delay
,
273 uint16_t override_interval
,
274 uint32_t dr_priority
,
275 uint32_t generation_id
,
276 struct list
*addr_list
)
278 struct pim_interface
*pim_ifp
;
279 struct pim_neighbor
*neigh
;
280 char src_str
[INET_ADDRSTRLEN
];
286 neigh
= XCALLOC(MTYPE_PIM_NEIGHBOR
, sizeof(*neigh
));
288 zlog_err("%s: PIM XCALLOC(%zu) failure",
289 __PRETTY_FUNCTION__
, sizeof(*neigh
));
293 neigh
->creation
= pim_time_monotonic_sec();
294 neigh
->source_addr
= source_addr
;
295 neigh
->hello_options
= hello_options
;
296 neigh
->propagation_delay_msec
= propagation_delay
;
297 neigh
->override_interval_msec
= override_interval
;
298 neigh
->dr_priority
= dr_priority
;
299 neigh
->generation_id
= generation_id
;
300 neigh
->prefix_list
= addr_list
;
301 neigh
->t_expire_timer
= NULL
;
302 neigh
->interface
= ifp
;
304 pim_neighbor_timer_reset(neigh
, holdtime
);
306 * The pim_ifstat_hello_sent variable is used to decide if
307 * we should expedite a hello out the interface. If we
308 * establish a new neighbor, we unfortunately need to
309 * reset the value so that we can know to hurry up and
312 pim_ifp
->pim_ifstat_hello_sent
= 0;
314 pim_inet4_dump("<src?>", source_addr
, src_str
, sizeof(src_str
));
316 if (PIM_DEBUG_PIM_EVENTS
) {
317 zlog_debug("%s: creating PIM neighbor %s on interface %s",
322 zlog_info("PIM NEIGHBOR UP: neighbor %s on interface %s",
325 if (neigh
->propagation_delay_msec
> pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
326 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
= neigh
->propagation_delay_msec
;
328 if (neigh
->override_interval_msec
> pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
329 pim_ifp
->pim_neighbors_highest_override_interval_msec
= neigh
->override_interval_msec
;
332 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
333 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
334 /* update num. of neighbors without hello option lan_delay */
335 ++pim_ifp
->pim_number_of_nonlandelay_neighbors
;
338 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
339 PIM_OPTION_MASK_DR_PRIORITY
)) {
340 /* update num. of neighbors without hello option dr_pri */
341 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
347 static void delete_prefix_list(struct pim_neighbor
*neigh
)
349 if (neigh
->prefix_list
) {
351 #ifdef DUMP_PREFIX_LIST
352 struct listnode
*p_node
;
355 int list_size
= neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1;
357 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, p_node
, p
)) {
358 pim_inet4_dump("<addr?>", p
->u
.prefix4
, addr_str
, sizeof(addr_str
));
359 zlog_debug("%s: DUMP_PREFIX_LIST neigh=%x prefix_list=%x prefix=%x addr=%s [%d/%d]",
361 (unsigned) neigh
, (unsigned) neigh
->prefix_list
, (unsigned) p
,
362 addr_str
, i
, list_size
);
367 list_delete(neigh
->prefix_list
);
368 neigh
->prefix_list
= 0;
372 void pim_neighbor_free(struct pim_neighbor
*neigh
)
374 zassert(!neigh
->t_expire_timer
);
376 delete_prefix_list(neigh
);
378 XFREE(MTYPE_PIM_NEIGHBOR
, neigh
);
381 struct pim_neighbor
*pim_neighbor_find(struct interface
*ifp
,
382 struct in_addr source_addr
)
384 struct pim_interface
*pim_ifp
;
385 struct listnode
*node
;
386 struct pim_neighbor
*neigh
;
392 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
393 if (source_addr
.s_addr
== neigh
->source_addr
.s_addr
) {
402 * Find the *one* interface out
403 * this interface. If more than
406 struct pim_neighbor
*
407 pim_neighbor_find_if (struct interface
*ifp
)
409 struct pim_interface
*pim_ifp
= ifp
->info
;
411 if (!pim_ifp
|| pim_ifp
->pim_neighbor_list
->count
!= 1)
414 return listnode_head (pim_ifp
->pim_neighbor_list
);
417 /* rpf info associated with an upstream entry needs to be re-evaluated
418 * when an RPF neighbor comes or goes */
420 pim_neighbor_rpf_update(void)
422 /* XXX: for the time being piggyback on the timer used on rib changes
423 * to scan and update the rpf nexthop. This is expensive processing
424 * and we should be able to optimize neighbor changes differently than
425 * nexthop changes. */
426 sched_rpf_cache_refresh();
429 struct pim_neighbor
*pim_neighbor_add(struct interface
*ifp
,
430 struct in_addr source_addr
,
431 pim_hello_options hello_options
,
433 uint16_t propagation_delay
,
434 uint16_t override_interval
,
435 uint32_t dr_priority
,
436 uint32_t generation_id
,
437 struct list
*addr_list
,
440 struct pim_interface
*pim_ifp
;
441 struct pim_neighbor
*neigh
;
443 neigh
= pim_neighbor_new(ifp
, source_addr
,
458 listnode_add(pim_ifp
->pim_neighbor_list
, neigh
);
461 RFC 4601: 4.3.2. DR Election
463 A router's idea of the current DR on an interface can change when a
464 PIM Hello message is received, when a neighbor times out, or when a
465 router's own DR Priority changes.
467 pim_if_dr_election(neigh
->interface
); // new neighbor -- should not trigger dr election...
470 RFC 4601: 4.3.1. Sending Hello Messages
472 To allow new or rebooting routers to learn of PIM neighbors quickly,
473 when a Hello message is received from a new neighbor, or a Hello
474 message with a new GenID is received from an existing neighbor, a
475 new Hello message should be sent on this interface after a
476 randomized delay between 0 and Triggered_Hello_Delay.
478 This is a bit silly to do it that way. If I get a new
479 genid we need to send the hello *now* because we've
480 lined up a bunch of join/prune messages to go out the
484 pim_hello_restart_now (ifp
);
486 pim_hello_restart_triggered(neigh
->interface
);
488 pim_upstream_find_new_rpf();
492 pim_neighbor_rpf_update();
497 find_neighbors_next_highest_propagation_delay_msec(struct interface
*ifp
,
498 struct pim_neighbor
*highest_neigh
)
500 struct pim_interface
*pim_ifp
;
501 struct listnode
*neigh_node
;
502 struct pim_neighbor
*neigh
;
503 uint16_t next_highest_delay_msec
;
508 next_highest_delay_msec
= pim_ifp
->pim_propagation_delay_msec
;
510 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
511 if (neigh
== highest_neigh
)
513 if (neigh
->propagation_delay_msec
> next_highest_delay_msec
)
514 next_highest_delay_msec
= neigh
->propagation_delay_msec
;
517 return next_highest_delay_msec
;
521 find_neighbors_next_highest_override_interval_msec(struct interface
*ifp
,
522 struct pim_neighbor
*highest_neigh
)
524 struct pim_interface
*pim_ifp
;
525 struct listnode
*neigh_node
;
526 struct pim_neighbor
*neigh
;
527 uint16_t next_highest_interval_msec
;
532 next_highest_interval_msec
= pim_ifp
->pim_override_interval_msec
;
534 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
535 if (neigh
== highest_neigh
)
537 if (neigh
->override_interval_msec
> next_highest_interval_msec
)
538 next_highest_interval_msec
= neigh
->override_interval_msec
;
541 return next_highest_interval_msec
;
544 void pim_neighbor_delete(struct interface
*ifp
,
545 struct pim_neighbor
*neigh
,
546 const char *delete_message
)
548 struct pim_interface
*pim_ifp
;
549 char src_str
[INET_ADDRSTRLEN
];
554 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
555 zlog_info("PIM NEIGHBOR DOWN: neighbor %s on interface %s: %s",
556 src_str
, ifp
->name
, delete_message
);
558 THREAD_OFF(neigh
->t_expire_timer
);
560 pim_if_assert_on_neighbor_down(ifp
, neigh
->source_addr
);
562 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
563 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
564 /* update num. of neighbors without hello option lan_delay */
566 --pim_ifp
->pim_number_of_nonlandelay_neighbors
;
569 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
570 PIM_OPTION_MASK_DR_PRIORITY
)) {
571 /* update num. of neighbors without dr_pri */
573 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
576 zassert(neigh
->propagation_delay_msec
<= pim_ifp
->pim_neighbors_highest_propagation_delay_msec
);
577 zassert(neigh
->override_interval_msec
<= pim_ifp
->pim_neighbors_highest_override_interval_msec
);
579 if (pim_if_lan_delay_enabled(ifp
)) {
581 /* will delete a neighbor with highest propagation delay? */
582 if (neigh
->propagation_delay_msec
== pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
583 /* then find the next highest propagation delay */
584 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
=
585 find_neighbors_next_highest_propagation_delay_msec(ifp
, neigh
);
588 /* will delete a neighbor with highest override interval? */
589 if (neigh
->override_interval_msec
== pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
590 /* then find the next highest propagation delay */
591 pim_ifp
->pim_neighbors_highest_override_interval_msec
=
592 find_neighbors_next_highest_override_interval_msec(ifp
, neigh
);
596 if (PIM_DEBUG_PIM_TRACE
) {
597 zlog_debug("%s: deleting PIM neighbor %s on interface %s",
602 listnode_delete(pim_ifp
->pim_neighbor_list
, neigh
);
604 pim_neighbor_free(neigh
);
606 pim_neighbor_rpf_update();
609 void pim_neighbor_delete_all(struct interface
*ifp
,
610 const char *delete_message
)
612 struct pim_interface
*pim_ifp
;
613 struct listnode
*neigh_node
;
614 struct listnode
*neigh_nextnode
;
615 struct pim_neighbor
*neigh
;
620 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_neighbor_list
, neigh_node
,
621 neigh_nextnode
, neigh
)) {
622 pim_neighbor_delete(ifp
, neigh
, delete_message
);
626 struct prefix
*pim_neighbor_find_secondary(struct pim_neighbor
*neigh
,
629 struct listnode
*node
;
632 if (!neigh
->prefix_list
)
635 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, node
, p
)) {
636 if (p
->family
== AF_INET
) {
637 if (addr
.s_addr
== p
->u
.prefix4
.s_addr
) {
647 RFC 4601: 4.3.4. Maintaining Secondary Address Lists
649 All the advertised secondary addresses in received Hello messages
650 must be checked against those previously advertised by all other
651 PIM neighbors on that interface. If there is a conflict and the
652 same secondary address was previously advertised by another
653 neighbor, then only the most recently received mapping MUST be
654 maintained, and an error message SHOULD be logged to the
655 administrator in a rate-limited manner.
657 static void delete_from_neigh_addr(struct interface
*ifp
,
658 struct list
*addr_list
,
659 struct in_addr neigh_addr
)
661 struct listnode
*addr_node
;
663 struct pim_interface
*pim_ifp
;
671 Scan secondary address list
673 for (ALL_LIST_ELEMENTS_RO(addr_list
, addr_node
,
675 struct listnode
*neigh_node
;
676 struct pim_neighbor
*neigh
;
678 if (addr
->family
!= AF_INET
)
684 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
,
687 struct prefix
*p
= pim_neighbor_find_secondary(neigh
, addr
->u
.prefix4
);
689 char addr_str
[INET_ADDRSTRLEN
];
690 char this_neigh_str
[INET_ADDRSTRLEN
];
691 char other_neigh_str
[INET_ADDRSTRLEN
];
693 pim_inet4_dump("<addr?>", addr
->u
.prefix4
, addr_str
, sizeof(addr_str
));
694 pim_inet4_dump("<neigh1?>", neigh_addr
, this_neigh_str
, sizeof(this_neigh_str
));
695 pim_inet4_dump("<neigh2?>", neigh
->source_addr
, other_neigh_str
, sizeof(other_neigh_str
));
697 zlog_info("secondary addr %s recvd from neigh %s deleted from neigh %s on %s",
698 addr_str
, this_neigh_str
, other_neigh_str
, ifp
->name
);
700 listnode_delete(neigh
->prefix_list
, p
);
705 } /* scan neighbors */
707 } /* scan addr list */
711 void pim_neighbor_update(struct pim_neighbor
*neigh
,
712 pim_hello_options hello_options
,
714 uint32_t dr_priority
,
715 struct list
*addr_list
)
717 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
719 /* Received holdtime ? */
720 if (PIM_OPTION_IS_SET(hello_options
, PIM_OPTION_MASK_HOLDTIME
)) {
721 pim_neighbor_timer_reset(neigh
, holdtime
);
724 pim_neighbor_timer_reset(neigh
, PIM_IF_DEFAULT_HOLDTIME(pim_ifp
));
727 #ifdef DUMP_PREFIX_LIST
728 zlog_debug("%s: DUMP_PREFIX_LIST old_prefix_list=%x old_size=%d new_prefix_list=%x new_size=%d",
730 (unsigned) neigh
->prefix_list
,
731 neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1,
732 (unsigned) addr_list
,
733 addr_list
? (int) listcount(addr_list
) : -1);
736 if (neigh
->prefix_list
== addr_list
) {
738 zlog_err("%s: internal error: trying to replace same prefix list=%p",
739 __PRETTY_FUNCTION__
, (void *) addr_list
);
743 /* Delete existing secondary address list */
744 delete_prefix_list(neigh
);
748 delete_from_neigh_addr(neigh
->interface
, addr_list
, neigh
->source_addr
);
751 /* Replace secondary address list */
752 neigh
->prefix_list
= addr_list
;
754 update_dr_priority(neigh
,
760 neigh
->hello_options
= hello_options
;