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,
32 #include "pim_neighbor.h"
35 #include "pim_iface.h"
37 #include "pim_upstream.h"
38 #include "pim_ifchannel.h"
40 #include "pim_zebra.h"
42 static void dr_election_by_addr(struct interface
*ifp
)
44 struct pim_interface
*pim_ifp
;
45 struct listnode
*node
;
46 struct pim_neighbor
*neigh
;
51 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
53 if (PIM_DEBUG_PIM_TRACE
) {
54 zlog_debug("%s: on interface %s",
59 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
60 if (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
)) {
61 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
66 static void dr_election_by_pri(struct interface
*ifp
)
68 struct pim_interface
*pim_ifp
;
69 struct listnode
*node
;
70 struct pim_neighbor
*neigh
;
76 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
77 dr_pri
= pim_ifp
->pim_dr_priority
;
79 if (PIM_DEBUG_PIM_TRACE
) {
80 zlog_debug("%s: dr pri %u on interface %s",
85 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
86 if (PIM_DEBUG_PIM_TRACE
) {
87 zlog_info("%s: neigh pri %u addr %x if dr addr %x",
90 ntohl(neigh
->source_addr
.s_addr
),
91 ntohl(pim_ifp
->pim_dr_addr
.s_addr
));
94 (neigh
->dr_priority
> dr_pri
) ||
96 (neigh
->dr_priority
== dr_pri
) &&
97 (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
))
100 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
101 dr_pri
= neigh
->dr_priority
;
107 RFC 4601: 4.3.2. DR Election
109 A router's idea of the current DR on an interface can change when a
110 PIM Hello message is received, when a neighbor times out, or when a
111 router's own DR Priority changes.
113 int pim_if_dr_election(struct interface
*ifp
)
115 struct pim_interface
*pim_ifp
= ifp
->info
;
116 struct in_addr old_dr_addr
;
118 ++pim_ifp
->pim_dr_election_count
;
120 old_dr_addr
= pim_ifp
->pim_dr_addr
;
122 if (pim_ifp
->pim_dr_num_nondrpri_neighbors
) {
123 dr_election_by_addr(ifp
);
126 dr_election_by_pri(ifp
);
130 if (old_dr_addr
.s_addr
!= pim_ifp
->pim_dr_addr
.s_addr
) {
132 if (PIM_DEBUG_PIM_EVENTS
) {
133 char dr_old_str
[INET_ADDRSTRLEN
];
134 char dr_new_str
[INET_ADDRSTRLEN
];
135 pim_inet4_dump("<old_dr?>", old_dr_addr
, dr_old_str
, sizeof(dr_old_str
));
136 pim_inet4_dump("<new_dr?>", pim_ifp
->pim_dr_addr
, dr_new_str
, sizeof(dr_new_str
));
137 zlog_debug("%s: DR was %s now is %s on interface %s",
139 dr_old_str
, dr_new_str
, ifp
->name
);
142 pim_ifp
->pim_dr_election_last
= pim_time_monotonic_sec(); /* timestamp */
143 ++pim_ifp
->pim_dr_election_changes
;
144 pim_if_update_join_desired(pim_ifp
);
145 pim_if_update_could_assert(ifp
);
146 pim_if_update_assert_tracking_desired(ifp
);
153 static void update_dr_priority(struct pim_neighbor
*neigh
,
154 pim_hello_options hello_options
,
155 uint32_t dr_priority
)
157 pim_hello_options will_set_pri
; /* boolean */
158 pim_hello_options bit_flip
; /* boolean */
159 pim_hello_options pri_change
; /* boolean */
161 will_set_pri
= PIM_OPTION_IS_SET(hello_options
,
162 PIM_OPTION_MASK_DR_PRIORITY
);
167 PIM_OPTION_IS_SET(neigh
->hello_options
, PIM_OPTION_MASK_DR_PRIORITY
)
171 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
173 /* update num. of neighbors without dr_pri */
176 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
179 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
187 (neigh
->dr_priority
!= dr_priority
)
191 neigh
->dr_priority
= dr_priority
;
194 neigh
->dr_priority
= 0; /* cosmetic unset */
199 RFC 4601: 4.3.2. DR Election
201 A router's idea of the current DR on an interface can change when a
202 PIM Hello message is received, when a neighbor times out, or when a
203 router's own DR Priority changes.
205 pim_if_dr_election(neigh
->interface
); // router's own DR Priority changes
209 static int on_neighbor_timer(struct thread
*t
)
211 struct pim_neighbor
*neigh
;
212 struct interface
*ifp
;
215 neigh
= THREAD_ARG(t
);
217 ifp
= neigh
->interface
;
219 if (PIM_DEBUG_PIM_TRACE
) {
220 char src_str
[INET_ADDRSTRLEN
];
221 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
222 zlog_debug("Expired %d sec holdtime for neighbor %s on interface %s",
223 neigh
->holdtime
, src_str
, ifp
->name
);
226 neigh
->t_expire_timer
= NULL
;
228 snprintf(msg
, sizeof(msg
), "%d-sec holdtime expired", neigh
->holdtime
);
229 pim_neighbor_delete(ifp
, neigh
, msg
);
232 RFC 4601: 4.3.2. DR Election
234 A router's idea of the current DR on an interface can change when a
235 PIM Hello message is received, when a neighbor times out, or when a
236 router's own DR Priority changes.
238 pim_if_dr_election(ifp
); // neighbor times out
243 void pim_neighbor_timer_reset(struct pim_neighbor
*neigh
, uint16_t holdtime
)
245 neigh
->holdtime
= holdtime
;
247 THREAD_OFF(neigh
->t_expire_timer
);
250 0xFFFF is request for no holdtime
252 if (neigh
->holdtime
== 0xFFFF) {
256 if (PIM_DEBUG_PIM_TRACE_DETAIL
) {
257 char src_str
[INET_ADDRSTRLEN
];
258 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
259 zlog_debug("%s: starting %u sec timer for neighbor %s on %s",
261 neigh
->holdtime
, src_str
, neigh
->interface
->name
);
264 THREAD_TIMER_ON(master
, neigh
->t_expire_timer
,
266 neigh
, neigh
->holdtime
);
269 static struct pim_neighbor
*pim_neighbor_new(struct interface
*ifp
,
270 struct in_addr source_addr
,
271 pim_hello_options hello_options
,
273 uint16_t propagation_delay
,
274 uint16_t override_interval
,
275 uint32_t dr_priority
,
276 uint32_t generation_id
,
277 struct list
*addr_list
)
279 struct pim_interface
*pim_ifp
;
280 struct pim_neighbor
*neigh
;
281 char src_str
[INET_ADDRSTRLEN
];
287 neigh
= XCALLOC(MTYPE_PIM_NEIGHBOR
, sizeof(*neigh
));
289 zlog_err("%s: PIM XCALLOC(%zu) failure",
290 __PRETTY_FUNCTION__
, sizeof(*neigh
));
294 neigh
->creation
= pim_time_monotonic_sec();
295 neigh
->source_addr
= source_addr
;
296 neigh
->hello_options
= hello_options
;
297 neigh
->propagation_delay_msec
= propagation_delay
;
298 neigh
->override_interval_msec
= override_interval
;
299 neigh
->dr_priority
= dr_priority
;
300 neigh
->generation_id
= generation_id
;
301 neigh
->prefix_list
= addr_list
;
302 neigh
->t_expire_timer
= NULL
;
303 neigh
->interface
= ifp
;
305 pim_neighbor_timer_reset(neigh
, holdtime
);
307 * The pim_ifstat_hello_sent variable is used to decide if
308 * we should expedite a hello out the interface. If we
309 * establish a new neighbor, we unfortunately need to
310 * reset the value so that we can know to hurry up and
313 pim_ifp
->pim_ifstat_hello_sent
= 0;
315 pim_inet4_dump("<src?>", source_addr
, src_str
, sizeof(src_str
));
317 if (PIM_DEBUG_PIM_EVENTS
) {
318 zlog_debug("%s: creating PIM neighbor %s on interface %s",
323 zlog_info("PIM NEIGHBOR UP: neighbor %s on interface %s",
326 if (neigh
->propagation_delay_msec
> pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
327 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
= neigh
->propagation_delay_msec
;
329 if (neigh
->override_interval_msec
> pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
330 pim_ifp
->pim_neighbors_highest_override_interval_msec
= neigh
->override_interval_msec
;
333 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
334 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
335 /* update num. of neighbors without hello option lan_delay */
336 ++pim_ifp
->pim_number_of_nonlandelay_neighbors
;
339 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
340 PIM_OPTION_MASK_DR_PRIORITY
)) {
341 /* update num. of neighbors without hello option dr_pri */
342 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
348 static void delete_prefix_list(struct pim_neighbor
*neigh
)
350 if (neigh
->prefix_list
) {
352 #ifdef DUMP_PREFIX_LIST
353 struct listnode
*p_node
;
356 int list_size
= neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1;
358 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, p_node
, p
)) {
359 pim_inet4_dump("<addr?>", p
->u
.prefix4
, addr_str
, sizeof(addr_str
));
360 zlog_debug("%s: DUMP_PREFIX_LIST neigh=%x prefix_list=%x prefix=%x addr=%s [%d/%d]",
362 (unsigned) neigh
, (unsigned) neigh
->prefix_list
, (unsigned) p
,
363 addr_str
, i
, list_size
);
368 list_delete(neigh
->prefix_list
);
369 neigh
->prefix_list
= 0;
373 void pim_neighbor_free(struct pim_neighbor
*neigh
)
375 zassert(!neigh
->t_expire_timer
);
377 delete_prefix_list(neigh
);
379 XFREE(MTYPE_PIM_NEIGHBOR
, neigh
);
382 struct pim_neighbor
*pim_neighbor_find(struct interface
*ifp
,
383 struct in_addr source_addr
)
385 struct pim_interface
*pim_ifp
;
386 struct listnode
*node
;
387 struct pim_neighbor
*neigh
;
393 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
394 if (source_addr
.s_addr
== neigh
->source_addr
.s_addr
) {
403 * Find the *one* interface out
404 * this interface. If more than
407 struct pim_neighbor
*
408 pim_neighbor_find_if (struct interface
*ifp
)
410 struct pim_interface
*pim_ifp
= ifp
->info
;
412 if (!pim_ifp
|| pim_ifp
->pim_neighbor_list
->count
!= 1)
415 return listnode_head (pim_ifp
->pim_neighbor_list
);
418 /* rpf info associated with an upstream entry needs to be re-evaluated
419 * when an RPF neighbor comes or goes */
421 pim_neighbor_rpf_update(void)
423 /* XXX: for the time being piggyback on the timer used on rib changes
424 * to scan and update the rpf nexthop. This is expensive processing
425 * and we should be able to optimize neighbor changes differently than
426 * nexthop changes. */
427 sched_rpf_cache_refresh();
430 struct pim_neighbor
*pim_neighbor_add(struct interface
*ifp
,
431 struct in_addr source_addr
,
432 pim_hello_options hello_options
,
434 uint16_t propagation_delay
,
435 uint16_t override_interval
,
436 uint32_t dr_priority
,
437 uint32_t generation_id
,
438 struct list
*addr_list
,
441 struct pim_interface
*pim_ifp
;
442 struct pim_neighbor
*neigh
;
444 neigh
= pim_neighbor_new(ifp
, source_addr
,
459 listnode_add(pim_ifp
->pim_neighbor_list
, neigh
);
462 RFC 4601: 4.3.2. DR Election
464 A router's idea of the current DR on an interface can change when a
465 PIM Hello message is received, when a neighbor times out, or when a
466 router's own DR Priority changes.
468 pim_if_dr_election(neigh
->interface
); // new neighbor -- should not trigger dr election...
471 RFC 4601: 4.3.1. Sending Hello Messages
473 To allow new or rebooting routers to learn of PIM neighbors quickly,
474 when a Hello message is received from a new neighbor, or a Hello
475 message with a new GenID is received from an existing neighbor, a
476 new Hello message should be sent on this interface after a
477 randomized delay between 0 and Triggered_Hello_Delay.
479 This is a bit silly to do it that way. If I get a new
480 genid we need to send the hello *now* because we've
481 lined up a bunch of join/prune messages to go out the
485 pim_hello_restart_now (ifp
);
487 pim_hello_restart_triggered(neigh
->interface
);
489 pim_upstream_find_new_rpf();
493 pim_neighbor_rpf_update();
498 find_neighbors_next_highest_propagation_delay_msec(struct interface
*ifp
,
499 struct pim_neighbor
*highest_neigh
)
501 struct pim_interface
*pim_ifp
;
502 struct listnode
*neigh_node
;
503 struct pim_neighbor
*neigh
;
504 uint16_t next_highest_delay_msec
;
509 next_highest_delay_msec
= pim_ifp
->pim_propagation_delay_msec
;
511 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
512 if (neigh
== highest_neigh
)
514 if (neigh
->propagation_delay_msec
> next_highest_delay_msec
)
515 next_highest_delay_msec
= neigh
->propagation_delay_msec
;
518 return next_highest_delay_msec
;
522 find_neighbors_next_highest_override_interval_msec(struct interface
*ifp
,
523 struct pim_neighbor
*highest_neigh
)
525 struct pim_interface
*pim_ifp
;
526 struct listnode
*neigh_node
;
527 struct pim_neighbor
*neigh
;
528 uint16_t next_highest_interval_msec
;
533 next_highest_interval_msec
= pim_ifp
->pim_override_interval_msec
;
535 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
536 if (neigh
== highest_neigh
)
538 if (neigh
->override_interval_msec
> next_highest_interval_msec
)
539 next_highest_interval_msec
= neigh
->override_interval_msec
;
542 return next_highest_interval_msec
;
545 void pim_neighbor_delete(struct interface
*ifp
,
546 struct pim_neighbor
*neigh
,
547 const char *delete_message
)
549 struct pim_interface
*pim_ifp
;
550 char src_str
[INET_ADDRSTRLEN
];
555 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
556 zlog_info("PIM NEIGHBOR DOWN: neighbor %s on interface %s: %s",
557 src_str
, ifp
->name
, delete_message
);
559 THREAD_OFF(neigh
->t_expire_timer
);
561 pim_if_assert_on_neighbor_down(ifp
, neigh
->source_addr
);
563 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
564 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
565 /* update num. of neighbors without hello option lan_delay */
567 --pim_ifp
->pim_number_of_nonlandelay_neighbors
;
570 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
571 PIM_OPTION_MASK_DR_PRIORITY
)) {
572 /* update num. of neighbors without dr_pri */
574 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
577 zassert(neigh
->propagation_delay_msec
<= pim_ifp
->pim_neighbors_highest_propagation_delay_msec
);
578 zassert(neigh
->override_interval_msec
<= pim_ifp
->pim_neighbors_highest_override_interval_msec
);
580 if (pim_if_lan_delay_enabled(ifp
)) {
582 /* will delete a neighbor with highest propagation delay? */
583 if (neigh
->propagation_delay_msec
== pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
584 /* then find the next highest propagation delay */
585 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
=
586 find_neighbors_next_highest_propagation_delay_msec(ifp
, neigh
);
589 /* will delete a neighbor with highest override interval? */
590 if (neigh
->override_interval_msec
== pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
591 /* then find the next highest propagation delay */
592 pim_ifp
->pim_neighbors_highest_override_interval_msec
=
593 find_neighbors_next_highest_override_interval_msec(ifp
, neigh
);
597 if (PIM_DEBUG_PIM_TRACE
) {
598 zlog_debug("%s: deleting PIM neighbor %s on interface %s",
603 listnode_delete(pim_ifp
->pim_neighbor_list
, neigh
);
605 pim_neighbor_free(neigh
);
607 pim_neighbor_rpf_update();
610 void pim_neighbor_delete_all(struct interface
*ifp
,
611 const char *delete_message
)
613 struct pim_interface
*pim_ifp
;
614 struct listnode
*neigh_node
;
615 struct listnode
*neigh_nextnode
;
616 struct pim_neighbor
*neigh
;
621 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_neighbor_list
, neigh_node
,
622 neigh_nextnode
, neigh
)) {
623 pim_neighbor_delete(ifp
, neigh
, delete_message
);
627 struct prefix
*pim_neighbor_find_secondary(struct pim_neighbor
*neigh
,
630 struct listnode
*node
;
633 if (!neigh
->prefix_list
)
636 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, node
, p
)) {
637 if (p
->family
== AF_INET
) {
638 if (addr
.s_addr
== p
->u
.prefix4
.s_addr
) {
648 RFC 4601: 4.3.4. Maintaining Secondary Address Lists
650 All the advertised secondary addresses in received Hello messages
651 must be checked against those previously advertised by all other
652 PIM neighbors on that interface. If there is a conflict and the
653 same secondary address was previously advertised by another
654 neighbor, then only the most recently received mapping MUST be
655 maintained, and an error message SHOULD be logged to the
656 administrator in a rate-limited manner.
658 static void delete_from_neigh_addr(struct interface
*ifp
,
659 struct list
*addr_list
,
660 struct in_addr neigh_addr
)
662 struct listnode
*addr_node
;
664 struct pim_interface
*pim_ifp
;
672 Scan secondary address list
674 for (ALL_LIST_ELEMENTS_RO(addr_list
, addr_node
,
676 struct listnode
*neigh_node
;
677 struct pim_neighbor
*neigh
;
679 if (addr
->family
!= AF_INET
)
685 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
,
688 struct prefix
*p
= pim_neighbor_find_secondary(neigh
, addr
->u
.prefix4
);
690 char addr_str
[INET_ADDRSTRLEN
];
691 char this_neigh_str
[INET_ADDRSTRLEN
];
692 char other_neigh_str
[INET_ADDRSTRLEN
];
694 pim_inet4_dump("<addr?>", addr
->u
.prefix4
, addr_str
, sizeof(addr_str
));
695 pim_inet4_dump("<neigh1?>", neigh_addr
, this_neigh_str
, sizeof(this_neigh_str
));
696 pim_inet4_dump("<neigh2?>", neigh
->source_addr
, other_neigh_str
, sizeof(other_neigh_str
));
698 zlog_info("secondary addr %s recvd from neigh %s deleted from neigh %s on %s",
699 addr_str
, this_neigh_str
, other_neigh_str
, ifp
->name
);
701 listnode_delete(neigh
->prefix_list
, p
);
706 } /* scan neighbors */
708 } /* scan addr list */
712 void pim_neighbor_update(struct pim_neighbor
*neigh
,
713 pim_hello_options hello_options
,
715 uint32_t dr_priority
,
716 struct list
*addr_list
)
718 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
720 /* Received holdtime ? */
721 if (PIM_OPTION_IS_SET(hello_options
, PIM_OPTION_MASK_HOLDTIME
)) {
722 pim_neighbor_timer_reset(neigh
, holdtime
);
725 pim_neighbor_timer_reset(neigh
, PIM_IF_DEFAULT_HOLDTIME(pim_ifp
));
728 #ifdef DUMP_PREFIX_LIST
729 zlog_debug("%s: DUMP_PREFIX_LIST old_prefix_list=%x old_size=%d new_prefix_list=%x new_size=%d",
731 (unsigned) neigh
->prefix_list
,
732 neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1,
733 (unsigned) addr_list
,
734 addr_list
? (int) listcount(addr_list
) : -1);
737 if (neigh
->prefix_list
== addr_list
) {
739 zlog_err("%s: internal error: trying to replace same prefix list=%p",
740 __PRETTY_FUNCTION__
, (void *) addr_list
);
744 /* Delete existing secondary address list */
745 delete_prefix_list(neigh
);
749 delete_from_neigh_addr(neigh
->interface
, addr_list
, neigh
->source_addr
);
752 /* Replace secondary address list */
753 neigh
->prefix_list
= addr_list
;
755 update_dr_priority(neigh
,
761 neigh
->hello_options
= hello_options
;