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,
29 #include "pim_neighbor.h"
32 #include "pim_iface.h"
34 #include "pim_upstream.h"
35 #include "pim_ifchannel.h"
37 static void dr_election_by_addr(struct interface
*ifp
)
39 struct pim_interface
*pim_ifp
;
40 struct listnode
*node
;
41 struct pim_neighbor
*neigh
;
46 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
48 if (PIM_DEBUG_PIM_TRACE
) {
49 zlog_debug("%s: on interface %s",
54 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
55 if (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
)) {
56 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
61 static void dr_election_by_pri(struct interface
*ifp
)
63 struct pim_interface
*pim_ifp
;
64 struct listnode
*node
;
65 struct pim_neighbor
*neigh
;
71 pim_ifp
->pim_dr_addr
= pim_ifp
->primary_address
;
72 dr_pri
= pim_ifp
->pim_dr_priority
;
74 if (PIM_DEBUG_PIM_TRACE
) {
75 zlog_debug("%s: dr pri %u on interface %s",
80 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
81 if (PIM_DEBUG_PIM_TRACE
) {
82 zlog_info("%s: neigh pri %u addr %x if dr addr %x",
85 ntohl(neigh
->source_addr
.s_addr
),
86 ntohl(pim_ifp
->pim_dr_addr
.s_addr
));
89 (neigh
->dr_priority
> dr_pri
) ||
91 (neigh
->dr_priority
== dr_pri
) &&
92 (ntohl(neigh
->source_addr
.s_addr
) > ntohl(pim_ifp
->pim_dr_addr
.s_addr
))
95 pim_ifp
->pim_dr_addr
= neigh
->source_addr
;
96 dr_pri
= neigh
->dr_priority
;
102 RFC 4601: 4.3.2. DR Election
104 A router's idea of the current DR on an interface can change when a
105 PIM Hello message is received, when a neighbor times out, or when a
106 router's own DR Priority changes.
108 int pim_if_dr_election(struct interface
*ifp
)
110 struct pim_interface
*pim_ifp
= ifp
->info
;
111 struct in_addr old_dr_addr
;
113 ++pim_ifp
->pim_dr_election_count
;
115 old_dr_addr
= pim_ifp
->pim_dr_addr
;
117 if (pim_ifp
->pim_dr_num_nondrpri_neighbors
) {
118 dr_election_by_addr(ifp
);
121 dr_election_by_pri(ifp
);
125 if (old_dr_addr
.s_addr
!= pim_ifp
->pim_dr_addr
.s_addr
) {
127 if (PIM_DEBUG_PIM_EVENTS
) {
128 char dr_old_str
[100];
129 char dr_new_str
[100];
130 pim_inet4_dump("<old_dr?>", old_dr_addr
, dr_old_str
, sizeof(dr_old_str
));
131 pim_inet4_dump("<new_dr?>", pim_ifp
->pim_dr_addr
, dr_new_str
, sizeof(dr_new_str
));
132 zlog_debug("%s: DR was %s now is %s on interface %s",
134 dr_old_str
, dr_new_str
, ifp
->name
);
137 pim_ifp
->pim_dr_election_last
= pim_time_monotonic_sec(); /* timestamp */
138 ++pim_ifp
->pim_dr_election_changes
;
139 pim_if_update_join_desired(pim_ifp
);
140 pim_if_update_could_assert(ifp
);
141 pim_if_update_assert_tracking_desired(ifp
);
148 static void update_dr_priority(struct pim_neighbor
*neigh
,
149 pim_hello_options hello_options
,
150 uint32_t dr_priority
)
152 pim_hello_options will_set_pri
; /* boolean */
153 pim_hello_options bit_flip
; /* boolean */
154 pim_hello_options pri_change
; /* boolean */
156 will_set_pri
= PIM_OPTION_IS_SET(hello_options
,
157 PIM_OPTION_MASK_DR_PRIORITY
);
162 PIM_OPTION_IS_SET(neigh
->hello_options
, PIM_OPTION_MASK_DR_PRIORITY
)
166 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
168 /* update num. of neighbors without dr_pri */
171 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
174 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
182 (neigh
->dr_priority
!= dr_priority
)
186 neigh
->dr_priority
= dr_priority
;
189 neigh
->dr_priority
= 0; /* cosmetic unset */
194 RFC 4601: 4.3.2. DR Election
196 A router's idea of the current DR on an interface can change when a
197 PIM Hello message is received, when a neighbor times out, or when a
198 router's own DR Priority changes.
200 pim_if_dr_election(neigh
->interface
); // router's own DR Priority changes
204 static int on_neighbor_timer(struct thread
*t
)
206 struct pim_neighbor
*neigh
;
207 struct interface
*ifp
;
211 neigh
= THREAD_ARG(t
);
214 ifp
= neigh
->interface
;
216 if (PIM_DEBUG_PIM_TRACE
) {
218 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
219 zlog_debug("Expired %d sec holdtime for neighbor %s on interface %s",
220 neigh
->holdtime
, src_str
, ifp
->name
);
223 neigh
->t_expire_timer
= 0;
225 snprintf(msg
, sizeof(msg
), "%d-sec holdtime expired", neigh
->holdtime
);
226 pim_neighbor_delete(ifp
, neigh
, msg
);
229 RFC 4601: 4.3.2. DR Election
231 A router's idea of the current DR on an interface can change when a
232 PIM Hello message is received, when a neighbor times out, or when a
233 router's own DR Priority changes.
235 pim_if_dr_election(ifp
); // neighbor times out
240 static void neighbor_timer_off(struct pim_neighbor
*neigh
)
242 if (PIM_DEBUG_PIM_TRACE_DETAIL
) {
243 if (neigh
->t_expire_timer
) {
245 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
246 zlog_debug("%s: cancelling timer for neighbor %s on %s",
248 src_str
, neigh
->interface
->name
);
251 THREAD_OFF(neigh
->t_expire_timer
);
252 zassert(!neigh
->t_expire_timer
);
255 void pim_neighbor_timer_reset(struct pim_neighbor
*neigh
, uint16_t holdtime
)
257 neigh
->holdtime
= holdtime
;
259 neighbor_timer_off(neigh
);
262 0xFFFF is request for no holdtime
264 if (neigh
->holdtime
== 0xFFFF) {
268 if (PIM_DEBUG_PIM_TRACE_DETAIL
) {
270 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
271 zlog_debug("%s: starting %u sec timer for neighbor %s on %s",
273 neigh
->holdtime
, src_str
, neigh
->interface
->name
);
276 THREAD_TIMER_ON(master
, neigh
->t_expire_timer
,
278 neigh
, neigh
->holdtime
);
281 static struct pim_neighbor
*pim_neighbor_new(struct interface
*ifp
,
282 struct in_addr source_addr
,
283 pim_hello_options hello_options
,
285 uint16_t propagation_delay
,
286 uint16_t override_interval
,
287 uint32_t dr_priority
,
288 uint32_t generation_id
,
289 struct list
*addr_list
)
291 struct pim_interface
*pim_ifp
;
292 struct pim_neighbor
*neigh
;
299 neigh
= XMALLOC(MTYPE_PIM_NEIGHBOR
, sizeof(*neigh
));
301 zlog_err("%s: PIM XMALLOC(%zu) failure",
302 __PRETTY_FUNCTION__
, sizeof(*neigh
));
306 neigh
->creation
= pim_time_monotonic_sec();
307 neigh
->source_addr
= source_addr
;
308 neigh
->hello_options
= hello_options
;
309 neigh
->propagation_delay_msec
= propagation_delay
;
310 neigh
->override_interval_msec
= override_interval
;
311 neigh
->dr_priority
= dr_priority
;
312 neigh
->generation_id
= generation_id
;
313 neigh
->prefix_list
= addr_list
;
314 neigh
->t_expire_timer
= 0;
315 neigh
->interface
= ifp
;
317 pim_neighbor_timer_reset(neigh
, holdtime
);
319 pim_inet4_dump("<src?>", source_addr
, src_str
, sizeof(src_str
));
321 if (PIM_DEBUG_PIM_EVENTS
) {
322 zlog_debug("%s: creating PIM neighbor %s on interface %s",
327 zlog_info("PIM NEIGHBOR UP: neighbor %s on interface %s",
330 if (neigh
->propagation_delay_msec
> pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
331 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
= neigh
->propagation_delay_msec
;
333 if (neigh
->override_interval_msec
> pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
334 pim_ifp
->pim_neighbors_highest_override_interval_msec
= neigh
->override_interval_msec
;
337 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
338 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
339 /* update num. of neighbors without hello option lan_delay */
340 ++pim_ifp
->pim_number_of_nonlandelay_neighbors
;
343 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
344 PIM_OPTION_MASK_DR_PRIORITY
)) {
345 /* update num. of neighbors without hello option dr_pri */
346 ++pim_ifp
->pim_dr_num_nondrpri_neighbors
;
352 static void delete_prefix_list(struct pim_neighbor
*neigh
)
354 if (neigh
->prefix_list
) {
356 #ifdef DUMP_PREFIX_LIST
357 struct listnode
*p_node
;
360 int list_size
= neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1;
362 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, p_node
, p
)) {
363 pim_inet4_dump("<addr?>", p
->u
.prefix4
, addr_str
, sizeof(addr_str
));
364 zlog_debug("%s: DUMP_PREFIX_LIST neigh=%x prefix_list=%x prefix=%x addr=%s [%d/%d]",
366 (unsigned) neigh
, (unsigned) neigh
->prefix_list
, (unsigned) p
,
367 addr_str
, i
, list_size
);
372 list_delete(neigh
->prefix_list
);
373 neigh
->prefix_list
= 0;
377 void pim_neighbor_free(struct pim_neighbor
*neigh
)
379 zassert(!neigh
->t_expire_timer
);
381 delete_prefix_list(neigh
);
383 XFREE(MTYPE_PIM_NEIGHBOR
, neigh
);
386 struct pim_neighbor
*pim_neighbor_find(struct interface
*ifp
,
387 struct in_addr source_addr
)
389 struct pim_interface
*pim_ifp
;
390 struct listnode
*node
;
391 struct pim_neighbor
*neigh
;
396 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, node
, neigh
)) {
397 if (source_addr
.s_addr
== neigh
->source_addr
.s_addr
) {
405 struct pim_neighbor
*pim_neighbor_add(struct interface
*ifp
,
406 struct in_addr source_addr
,
407 pim_hello_options hello_options
,
409 uint16_t propagation_delay
,
410 uint16_t override_interval
,
411 uint32_t dr_priority
,
412 uint32_t generation_id
,
413 struct list
*addr_list
)
415 struct pim_interface
*pim_ifp
;
416 struct pim_neighbor
*neigh
;
418 neigh
= pim_neighbor_new(ifp
, source_addr
,
433 listnode_add(pim_ifp
->pim_neighbor_list
, neigh
);
436 RFC 4601: 4.3.2. DR Election
438 A router's idea of the current DR on an interface can change when a
439 PIM Hello message is received, when a neighbor times out, or when a
440 router's own DR Priority changes.
442 pim_if_dr_election(neigh
->interface
); // new neighbor -- should not trigger dr election...
445 RFC 4601: 4.3.1. Sending Hello Messages
447 To allow new or rebooting routers to learn of PIM neighbors quickly,
448 when a Hello message is received from a new neighbor, or a Hello
449 message with a new GenID is received from an existing neighbor, a
450 new Hello message should be sent on this interface after a
451 randomized delay between 0 and Triggered_Hello_Delay.
453 pim_hello_restart_triggered(neigh
->interface
);
459 find_neighbors_next_highest_propagation_delay_msec(struct interface
*ifp
,
460 struct pim_neighbor
*highest_neigh
)
462 struct pim_interface
*pim_ifp
;
463 struct listnode
*neigh_node
;
464 struct pim_neighbor
*neigh
;
465 uint16_t next_highest_delay_msec
;
470 next_highest_delay_msec
= pim_ifp
->pim_propagation_delay_msec
;
472 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
473 if (neigh
== highest_neigh
)
475 if (neigh
->propagation_delay_msec
> next_highest_delay_msec
)
476 next_highest_delay_msec
= neigh
->propagation_delay_msec
;
479 return next_highest_delay_msec
;
483 find_neighbors_next_highest_override_interval_msec(struct interface
*ifp
,
484 struct pim_neighbor
*highest_neigh
)
486 struct pim_interface
*pim_ifp
;
487 struct listnode
*neigh_node
;
488 struct pim_neighbor
*neigh
;
489 uint16_t next_highest_interval_msec
;
494 next_highest_interval_msec
= pim_ifp
->pim_override_interval_msec
;
496 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
, neigh
)) {
497 if (neigh
== highest_neigh
)
499 if (neigh
->override_interval_msec
> next_highest_interval_msec
)
500 next_highest_interval_msec
= neigh
->override_interval_msec
;
503 return next_highest_interval_msec
;
506 void pim_neighbor_delete(struct interface
*ifp
,
507 struct pim_neighbor
*neigh
,
508 const char *delete_message
)
510 struct pim_interface
*pim_ifp
;
516 pim_inet4_dump("<src?>", neigh
->source_addr
, src_str
, sizeof(src_str
));
517 zlog_info("PIM NEIGHBOR DOWN: neighbor %s on interface %s: %s",
518 src_str
, ifp
->name
, delete_message
);
520 neighbor_timer_off(neigh
);
522 pim_if_assert_on_neighbor_down(ifp
, neigh
->source_addr
);
524 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
525 PIM_OPTION_MASK_LAN_PRUNE_DELAY
)) {
526 /* update num. of neighbors without hello option lan_delay */
528 --pim_ifp
->pim_number_of_nonlandelay_neighbors
;
531 if (!PIM_OPTION_IS_SET(neigh
->hello_options
,
532 PIM_OPTION_MASK_DR_PRIORITY
)) {
533 /* update num. of neighbors without dr_pri */
535 --pim_ifp
->pim_dr_num_nondrpri_neighbors
;
538 zassert(neigh
->propagation_delay_msec
<= pim_ifp
->pim_neighbors_highest_propagation_delay_msec
);
539 zassert(neigh
->override_interval_msec
<= pim_ifp
->pim_neighbors_highest_override_interval_msec
);
541 if (pim_if_lan_delay_enabled(ifp
)) {
543 /* will delete a neighbor with highest propagation delay? */
544 if (neigh
->propagation_delay_msec
== pim_ifp
->pim_neighbors_highest_propagation_delay_msec
) {
545 /* then find the next highest propagation delay */
546 pim_ifp
->pim_neighbors_highest_propagation_delay_msec
=
547 find_neighbors_next_highest_propagation_delay_msec(ifp
, neigh
);
550 /* will delete a neighbor with highest override interval? */
551 if (neigh
->override_interval_msec
== pim_ifp
->pim_neighbors_highest_override_interval_msec
) {
552 /* then find the next highest propagation delay */
553 pim_ifp
->pim_neighbors_highest_override_interval_msec
=
554 find_neighbors_next_highest_override_interval_msec(ifp
, neigh
);
558 if (PIM_DEBUG_PIM_TRACE
) {
559 zlog_debug("%s: deleting PIM neighbor %s on interface %s",
564 listnode_delete(pim_ifp
->pim_neighbor_list
, neigh
);
566 pim_neighbor_free(neigh
);
569 void pim_neighbor_delete_all(struct interface
*ifp
,
570 const char *delete_message
)
572 struct pim_interface
*pim_ifp
;
573 struct listnode
*neigh_node
;
574 struct listnode
*neigh_nextnode
;
575 struct pim_neighbor
*neigh
;
580 for (ALL_LIST_ELEMENTS(pim_ifp
->pim_neighbor_list
, neigh_node
,
581 neigh_nextnode
, neigh
)) {
582 pim_neighbor_delete(ifp
, neigh
, delete_message
);
586 struct prefix
*pim_neighbor_find_secondary(struct pim_neighbor
*neigh
,
589 struct listnode
*node
;
592 if (!neigh
->prefix_list
)
595 for (ALL_LIST_ELEMENTS_RO(neigh
->prefix_list
, node
, p
)) {
596 if (p
->family
== AF_INET
) {
597 if (addr
.s_addr
== p
->u
.prefix4
.s_addr
) {
607 RFC 4601: 4.3.4. Maintaining Secondary Address Lists
609 All the advertised secondary addresses in received Hello messages
610 must be checked against those previously advertised by all other
611 PIM neighbors on that interface. If there is a conflict and the
612 same secondary address was previously advertised by another
613 neighbor, then only the most recently received mapping MUST be
614 maintained, and an error message SHOULD be logged to the
615 administrator in a rate-limited manner.
617 static void delete_from_neigh_addr(struct interface
*ifp
,
618 struct list
*addr_list
,
619 struct in_addr neigh_addr
)
621 struct listnode
*addr_node
;
623 struct pim_interface
*pim_ifp
;
631 Scan secondary address list
633 for (ALL_LIST_ELEMENTS_RO(addr_list
, addr_node
,
635 struct listnode
*neigh_node
;
636 struct pim_neighbor
*neigh
;
638 if (addr
->family
!= AF_INET
)
644 for (ALL_LIST_ELEMENTS_RO(pim_ifp
->pim_neighbor_list
, neigh_node
,
647 struct prefix
*p
= pim_neighbor_find_secondary(neigh
, addr
->u
.prefix4
);
650 char this_neigh_str
[100];
651 char other_neigh_str
[100];
653 pim_inet4_dump("<addr?>", addr
->u
.prefix4
, addr_str
, sizeof(addr_str
));
654 pim_inet4_dump("<neigh1?>", neigh_addr
, this_neigh_str
, sizeof(this_neigh_str
));
655 pim_inet4_dump("<neigh2?>", neigh
->source_addr
, other_neigh_str
, sizeof(other_neigh_str
));
657 zlog_info("secondary addr %s recvd from neigh %s deleted from neigh %s on %s",
658 addr_str
, this_neigh_str
, other_neigh_str
, ifp
->name
);
660 listnode_delete(neigh
->prefix_list
, p
);
665 } /* scan neighbors */
667 } /* scan addr list */
671 void pim_neighbor_update(struct pim_neighbor
*neigh
,
672 pim_hello_options hello_options
,
674 uint32_t dr_priority
,
675 struct list
*addr_list
)
677 struct pim_interface
*pim_ifp
= neigh
->interface
->info
;
679 /* Received holdtime ? */
680 if (PIM_OPTION_IS_SET(hello_options
, PIM_OPTION_MASK_HOLDTIME
)) {
681 pim_neighbor_timer_reset(neigh
, holdtime
);
684 pim_neighbor_timer_reset(neigh
, PIM_IF_DEFAULT_HOLDTIME(pim_ifp
));
687 #ifdef DUMP_PREFIX_LIST
688 zlog_debug("%s: DUMP_PREFIX_LIST old_prefix_list=%x old_size=%d new_prefix_list=%x new_size=%d",
690 (unsigned) neigh
->prefix_list
,
691 neigh
->prefix_list
? (int) listcount(neigh
->prefix_list
) : -1,
692 (unsigned) addr_list
,
693 addr_list
? (int) listcount(addr_list
) : -1);
696 if (neigh
->prefix_list
== addr_list
) {
698 zlog_err("%s: internal error: trying to replace same prefix list=%p",
699 __PRETTY_FUNCTION__
, (void *) addr_list
);
703 /* Delete existing secondary address list */
704 delete_prefix_list(neigh
);
708 delete_from_neigh_addr(neigh
->interface
, addr_list
, neigh
->source_addr
);
711 /* Replace secondary address list */
712 neigh
->prefix_list
= addr_list
;
714 update_dr_priority(neigh
,
720 neigh
->hello_options
= hello_options
;