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,
20 $QuaggaId: $Format:%an, %ai, %h$ $
31 #include "pim_neighbor.h"
34 #include "pim_iface.h"
36 #include "pim_upstream.h"
37 #include "pim_ifchannel.h"
39 static void dr_election_by_addr(struct interface
*ifp
)
41 struct pim_interface
*pim_ifp
;
42 struct listnode
*node
;
43 struct pim_neighbor
*neigh
;
48 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
50 if (PIM_DEBUG_PIM_TRACE
) {
51 zlog_debug("%s: on interface %s",
56 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
57 if (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
)) {
58 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
63 static void dr_election_by_pri(struct interface
*ifp
)
65 struct pim_interface
*pim_ifp
;
66 struct listnode
*node
;
67 struct pim_neighbor
*neigh
;
73 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
74 dr_pri
= pim_ifp
->pim_dr_priority
;
76 if (PIM_DEBUG_PIM_TRACE
) {
77 zlog_debug("%s: dr pri %u on interface %s",
82 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
83 if (PIM_DEBUG_PIM_TRACE
) {
84 zlog_info("%s: neigh pri %u addr %x if dr addr %x",
87 ntohl(neigh
->source_addr
.s_addr
),
88 ntohl(pim_ifp
->pim_dr_addr
.s_addr
));
91 (neigh
->dr_priority
> dr_pri
) ||
93 (neigh
->dr_priority
== dr_pri
) &&
94 (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
))
97 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
98 dr_pri
= neigh
->dr_priority
;
104 RFC 4601: 4.3.2. DR Election
106 A router's idea of the current DR on an interface can change when a
107 PIM Hello message is received, when a neighbor times out, or when a
108 router's own DR Priority changes.
110 int pim_if_dr_election(struct interface
*ifp
)
112 struct pim_interface
*pim_ifp
= ifp
->info
;
113 struct in_addr old_dr_addr
;
115 ++pim_ifp
->pim_dr_election_count
;
117 old_dr_addr
= pim_ifp
->pim_dr_addr
;
119 if (pim_ifp
->pim_dr_num_nondrpri_neighbors
) {
120 dr_election_by_addr(ifp
);
123 dr_election_by_pri(ifp
);
127 if (old_dr_addr
.s_addr
!= pim_ifp
->pim_dr_addr
.s_addr
) {
129 if (PIM_DEBUG_PIM_EVENTS
) {
130 char dr_old_str
[100];
131 char dr_new_str
[100];
132 pim_inet4_dump("<old_dr?>", old_dr_addr
, dr_old_str
, sizeof(dr_old_str
));
133 pim_inet4_dump("<new_dr?>", pim_ifp
->pim_dr_addr
, dr_new_str
, sizeof(dr_new_str
));
134 zlog_debug("%s: DR was %s now is %s on interface %s",
136 dr_old_str
, dr_new_str
, ifp
->name
);
139 pim_ifp
->pim_dr_election_last
= pim_time_monotonic_sec(); /* timestamp */
140 ++pim_ifp
->pim_dr_election_changes
;
141 pim_if_update_join_desired(pim_ifp
);
142 pim_if_update_could_assert(ifp
);
143 pim_if_update_assert_tracking_desired(ifp
);
150 static void update_dr_priority(struct pim_neighbor
*neigh
,
151 pim_hello_options hello_options
,
152 uint32_t dr_priority
)
154 pim_hello_options will_set_pri
; /* boolean */
155 pim_hello_options bit_flip
; /* boolean */
156 pim_hello_options pri_change
; /* boolean */
158 will_set_pri
= PIM_OPTION_IS_SET(hello_options
,
159 PIM_OPTION_MASK_DR_PRIORITY
);
164 PIM_OPTION_IS_SET(neigh
->hello_options
, PIM_OPTION_MASK_DR_PRIORITY
)
168 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
170 /* update num. of neighbors without dr_pri */
173 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
176 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
184 (neigh
->dr_priority
!= dr_priority
)
188 neigh
->dr_priority
= dr_priority
;
191 neigh
->dr_priority
= 0; /* cosmetic unset */
196 RFC 4601: 4.3.2. DR Election
198 A router's idea of the current DR on an interface can change when a
199 PIM Hello message is received, when a neighbor times out, or when a
200 router's own DR Priority changes.
202 pim_if_dr_election(neigh
->interface
); // router's own DR Priority changes
206 static int on_neighbor_timer(struct thread
*t
)
208 struct pim_neighbor
*neigh
;
209 struct interface
*ifp
;
213 neigh
= THREAD_ARG(t
);
216 ifp
= neigh
->interface
;
218 if (PIM_DEBUG_PIM_TRACE
) {
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
= 0;
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 static void neighbor_timer_off(struct pim_neighbor
*neigh
)
244 if (PIM_DEBUG_PIM_TRACE_DETAIL
) {
245 if (neigh
->t_expire_timer
) {
247 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
248 zlog_debug("%s: cancelling timer for neighbor %s on %s",
250 src_str
, neigh
->interface
->name
);
253 THREAD_OFF(neigh
->t_expire_timer
);
254 zassert(!neigh
->t_expire_timer
);
257 void pim_neighbor_timer_reset(struct pim_neighbor
*neigh
, uint16_t holdtime
)
259 neigh
->holdtime
= holdtime
;
261 neighbor_timer_off(neigh
);
264 0xFFFF is request for no holdtime
266 if (neigh
->holdtime
== 0xFFFF) {
270 if (PIM_DEBUG_PIM_TRACE_DETAIL
) {
272 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
273 zlog_debug("%s: starting %u sec timer for neighbor %s on %s",
275 neigh
->holdtime
, src_str
, neigh
->interface
->name
);
278 THREAD_TIMER_ON(master
, neigh
->t_expire_timer
,
280 neigh
, neigh
->holdtime
);
283 static struct pim_neighbor
*pim_neighbor_new(struct interface
*ifp
,
284 struct in_addr source_addr
,
285 pim_hello_options hello_options
,
287 uint16_t propagation_delay
,
288 uint16_t override_interval
,
289 uint32_t dr_priority
,
290 uint32_t generation_id
,
291 struct list
*addr_list
)
293 struct pim_interface
*pim_ifp
;
294 struct pim_neighbor
*neigh
;
301 neigh
= XMALLOC(MTYPE_PIM_NEIGHBOR
, sizeof(*neigh
));
303 zlog_err("%s: PIM XMALLOC(%zu) failure",
304 __PRETTY_FUNCTION__
, sizeof(*neigh
));
308 neigh
->creation
= pim_time_monotonic_sec();
309 neigh
->source_addr
= source_addr
;
310 neigh
->hello_options
= hello_options
;
311 neigh
->propagation_delay_msec
= propagation_delay
;
312 neigh
->override_interval_msec
= override_interval
;
313 neigh
->dr_priority
= dr_priority
;
314 neigh
->generation_id
= generation_id
;
315 neigh
->prefix_list
= addr_list
;
316 neigh
->t_expire_timer
= 0;
317 neigh
->interface
= ifp
;
319 pim_neighbor_timer_reset(neigh
, holdtime
);
321 pim_inet4_dump("<src?>", source_addr
, src_str
, sizeof(src_str
));
323 if (PIM_DEBUG_PIM_EVENTS
) {
324 zlog_debug("%s: creating PIM neighbor %s on interface %s",
329 zlog_info("PIM NEIGHBOR UP: neighbor %s on interface %s",
332 if (neigh
->propagation_delay_msec
> pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
333 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
= neigh
->propagation_delay_msec
;
335 if (neigh
->override_interval_msec
> pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
336 pim_ifp
->pim_neighbors_highest_override_interval_msec
= neigh
->override_interval_msec
;
339 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
340 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
341 /* update num. of neighbors without hello option lan_delay */
342 ++pim_ifp
->pim_number_of_nonlandelay_neighbors
;
345 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
346 PIM_OPTION_MASK_DR_PRIORITY
)) {
347 /* update num. of neighbors without hello option dr_pri */
348 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
354 static void delete_prefix_list(struct pim_neighbor
*neigh
)
356 if (neigh
->prefix_list
) {
358 #ifdef DUMP_PREFIX_LIST
359 struct listnode
*p_node
;
362 int list_size
= neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1;
364 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, p_node
, p
)) {
365 pim_inet4_dump("<addr?>", p
->u
.prefix4
, addr_str
, sizeof(addr_str
));
366 zlog_debug("%s: DUMP_PREFIX_LIST neigh=%x prefix_list=%x prefix=%x addr=%s [%d/%d]",
368 (unsigned) neigh
, (unsigned) neigh
->prefix_list
, (unsigned) p
,
369 addr_str
, i
, list_size
);
374 list_delete(neigh
->prefix_list
);
375 neigh
->prefix_list
= 0;
379 void pim_neighbor_free(struct pim_neighbor
*neigh
)
381 zassert(!neigh
->t_expire_timer
);
383 delete_prefix_list(neigh
);
385 XFREE(MTYPE_PIM_NEIGHBOR
, neigh
);
388 struct pim_neighbor
*pim_neighbor_find(struct interface
*ifp
,
389 struct in_addr source_addr
)
391 struct pim_interface
*pim_ifp
;
392 struct listnode
*node
;
393 struct pim_neighbor
*neigh
;
398 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
399 if (source_addr
.s_addr
== neigh
->source_addr
.s_addr
) {
407 struct pim_neighbor
*pim_neighbor_add(struct interface
*ifp
,
408 struct in_addr source_addr
,
409 pim_hello_options hello_options
,
411 uint16_t propagation_delay
,
412 uint16_t override_interval
,
413 uint32_t dr_priority
,
414 uint32_t generation_id
,
415 struct list
*addr_list
)
417 struct pim_interface
*pim_ifp
;
418 struct pim_neighbor
*neigh
;
420 neigh
= pim_neighbor_new(ifp
, source_addr
,
435 listnode_add(pim_ifp
->pim_neighbor_list
, neigh
);
438 RFC 4601: 4.3.2. DR Election
440 A router's idea of the current DR on an interface can change when a
441 PIM Hello message is received, when a neighbor times out, or when a
442 router's own DR Priority changes.
444 pim_if_dr_election(neigh
->interface
); // new neighbor -- should not trigger dr election...
447 RFC 4601: 4.3.1. Sending Hello Messages
449 To allow new or rebooting routers to learn of PIM neighbors quickly,
450 when a Hello message is received from a new neighbor, or a Hello
451 message with a new GenID is received from an existing neighbor, a
452 new Hello message should be sent on this interface after a
453 randomized delay between 0 and Triggered_Hello_Delay.
455 pim_hello_restart_triggered(neigh
->interface
);
461 find_neighbors_next_highest_propagation_delay_msec(struct interface
*ifp
,
462 struct pim_neighbor
*highest_neigh
)
464 struct pim_interface
*pim_ifp
;
465 struct listnode
*neigh_node
;
466 struct pim_neighbor
*neigh
;
467 uint16_t next_highest_delay_msec
;
472 next_highest_delay_msec
= pim_ifp
->pim_propagation_delay_msec
;
474 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
475 if (neigh
== highest_neigh
)
477 if (neigh
->propagation_delay_msec
> next_highest_delay_msec
)
478 next_highest_delay_msec
= neigh
->propagation_delay_msec
;
481 return next_highest_delay_msec
;
485 find_neighbors_next_highest_override_interval_msec(struct interface
*ifp
,
486 struct pim_neighbor
*highest_neigh
)
488 struct pim_interface
*pim_ifp
;
489 struct listnode
*neigh_node
;
490 struct pim_neighbor
*neigh
;
491 uint16_t next_highest_interval_msec
;
496 next_highest_interval_msec
= pim_ifp
->pim_override_interval_msec
;
498 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
499 if (neigh
== highest_neigh
)
501 if (neigh
->override_interval_msec
> next_highest_interval_msec
)
502 next_highest_interval_msec
= neigh
->override_interval_msec
;
505 return next_highest_interval_msec
;
508 void pim_neighbor_delete(struct interface
*ifp
,
509 struct pim_neighbor
*neigh
,
510 const char *delete_message
)
512 struct pim_interface
*pim_ifp
;
518 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
519 zlog_info("PIM NEIGHBOR DOWN: neighbor %s on interface %s: %s",
520 src_str
, ifp
->name
, delete_message
);
522 neighbor_timer_off(neigh
);
524 pim_if_assert_on_neighbor_down(ifp
, neigh
->source_addr
);
526 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
527 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
528 /* update num. of neighbors without hello option lan_delay */
530 --pim_ifp
->pim_number_of_nonlandelay_neighbors
;
533 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
534 PIM_OPTION_MASK_DR_PRIORITY
)) {
535 /* update num. of neighbors without dr_pri */
537 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
540 zassert(neigh
->propagation_delay_msec
<= pim_ifp
->pim_neighbors_highest_propagation_delay_msec
);
541 zassert(neigh
->override_interval_msec
<= pim_ifp
->pim_neighbors_highest_override_interval_msec
);
543 if (pim_if_lan_delay_enabled(ifp
)) {
545 /* will delete a neighbor with highest propagation delay? */
546 if (neigh
->propagation_delay_msec
== pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
547 /* then find the next highest propagation delay */
548 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
=
549 find_neighbors_next_highest_propagation_delay_msec(ifp
, neigh
);
552 /* will delete a neighbor with highest override interval? */
553 if (neigh
->override_interval_msec
== pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
554 /* then find the next highest propagation delay */
555 pim_ifp
->pim_neighbors_highest_override_interval_msec
=
556 find_neighbors_next_highest_override_interval_msec(ifp
, neigh
);
560 if (PIM_DEBUG_PIM_TRACE
) {
561 zlog_debug("%s: deleting PIM neighbor %s on interface %s",
566 listnode_delete(pim_ifp
->pim_neighbor_list
, neigh
);
568 pim_neighbor_free(neigh
);
571 void pim_neighbor_delete_all(struct interface
*ifp
,
572 const char *delete_message
)
574 struct pim_interface
*pim_ifp
;
575 struct listnode
*neigh_node
;
576 struct listnode
*neigh_nextnode
;
577 struct pim_neighbor
*neigh
;
582 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_neighbor_list
, neigh_node
,
583 neigh_nextnode
, neigh
)) {
584 pim_neighbor_delete(ifp
, neigh
, delete_message
);
588 struct prefix
*pim_neighbor_find_secondary(struct pim_neighbor
*neigh
,
591 struct listnode
*node
;
594 if (!neigh
->prefix_list
)
597 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, node
, p
)) {
598 if (p
->family
== AF_INET
) {
599 if (addr
.s_addr
== p
->u
.prefix4
.s_addr
) {
609 RFC 4601: 4.3.4. Maintaining Secondary Address Lists
611 All the advertised secondary addresses in received Hello messages
612 must be checked against those previously advertised by all other
613 PIM neighbors on that interface. If there is a conflict and the
614 same secondary address was previously advertised by another
615 neighbor, then only the most recently received mapping MUST be
616 maintained, and an error message SHOULD be logged to the
617 administrator in a rate-limited manner.
619 static void delete_from_neigh_addr(struct interface
*ifp
,
620 struct list
*addr_list
,
621 struct in_addr neigh_addr
)
623 struct listnode
*addr_node
;
625 struct pim_interface
*pim_ifp
;
633 Scan secondary address list
635 for (ALL_LIST_ELEMENTS_RO(addr_list
, addr_node
,
637 struct listnode
*neigh_node
;
638 struct pim_neighbor
*neigh
;
640 if (addr
->family
!= AF_INET
)
646 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
,
649 struct prefix
*p
= pim_neighbor_find_secondary(neigh
, addr
->u
.prefix4
);
652 char this_neigh_str
[100];
653 char other_neigh_str
[100];
655 pim_inet4_dump("<addr?>", addr
->u
.prefix4
, addr_str
, sizeof(addr_str
));
656 pim_inet4_dump("<neigh1?>", neigh_addr
, this_neigh_str
, sizeof(this_neigh_str
));
657 pim_inet4_dump("<neigh2?>", neigh
->source_addr
, other_neigh_str
, sizeof(other_neigh_str
));
659 zlog_info("secondary addr %s recvd from neigh %s deleted from neigh %s on %s",
660 addr_str
, this_neigh_str
, other_neigh_str
, ifp
->name
);
662 listnode_delete(neigh
->prefix_list
, p
);
667 } /* scan neighbors */
669 } /* scan addr list */
673 void pim_neighbor_update(struct pim_neighbor
*neigh
,
674 pim_hello_options hello_options
,
676 uint32_t dr_priority
,
677 struct list
*addr_list
)
679 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
681 /* Received holdtime ? */
682 if (PIM_OPTION_IS_SET(hello_options
, PIM_OPTION_MASK_HOLDTIME
)) {
683 pim_neighbor_timer_reset(neigh
, holdtime
);
686 pim_neighbor_timer_reset(neigh
, PIM_IF_DEFAULT_HOLDTIME(pim_ifp
));
689 #ifdef DUMP_PREFIX_LIST
690 zlog_debug("%s: DUMP_PREFIX_LIST old_prefix_list=%x old_size=%d new_prefix_list=%x new_size=%d",
692 (unsigned) neigh
->prefix_list
,
693 neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1,
694 (unsigned) addr_list
,
695 addr_list
? (int) listcount(addr_list
) : -1);
698 if (neigh
->prefix_list
== addr_list
) {
700 zlog_err("%s: internal error: trying to replace same prefix list=%p",
701 __PRETTY_FUNCTION__
, (void *) addr_list
);
705 /* Delete existing secondary address list */
706 delete_prefix_list(neigh
);
710 delete_from_neigh_addr(neigh
->interface
, addr_list
, neigh
->source_addr
);
713 /* Replace secondary address list */
714 neigh
->prefix_list
= addr_list
;
716 update_dr_priority(neigh
,
722 neigh
->hello_options
= hello_options
;