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$ $
30 #include "pim_neighbor.h"
33 #include "pim_iface.h"
35 #include "pim_upstream.h"
36 #include "pim_ifchannel.h"
38 static void dr_election_by_addr(struct interface *ifp)
40 struct pim_interface *pim_ifp;
41 struct listnode *node;
42 struct pim_neighbor *neigh;
47 pim_ifp->pim_dr_addr = pim_ifp->primary_address;
49 if (PIM_DEBUG_PIM_TRACE) {
50 zlog_debug("%s: on interface %s",
55 for (ALL_LIST_ELEMENTS_RO(pim_ifp->pim_neighbor_list, node, neigh)) {
56 if (ntohl(neigh->source_addr.s_addr) > ntohl(pim_ifp->pim_dr_addr.s_addr)) {
57 pim_ifp->pim_dr_addr = neigh->source_addr;
62 static void dr_election_by_pri(struct interface *ifp)
64 struct pim_interface *pim_ifp;
65 struct listnode *node;
66 struct pim_neighbor *neigh;
72 pim_ifp->pim_dr_addr = pim_ifp->primary_address;
73 dr_pri = pim_ifp->pim_dr_priority;
75 if (PIM_DEBUG_PIM_TRACE) {
76 zlog_debug("%s: dr pri %u on interface %s",
81 for (ALL_LIST_ELEMENTS_RO(pim_ifp->pim_neighbor_list, node, neigh)) {
82 if (PIM_DEBUG_PIM_TRACE) {
83 zlog_info("%s: neigh pri %u addr %x if dr addr %x",
86 ntohl(neigh->source_addr.s_addr),
87 ntohl(pim_ifp->pim_dr_addr.s_addr));
90 (neigh->dr_priority > dr_pri) ||
92 (neigh->dr_priority == dr_pri) &&
93 (ntohl(neigh->source_addr.s_addr) > ntohl(pim_ifp->pim_dr_addr.s_addr))
96 pim_ifp->pim_dr_addr = neigh->source_addr;
97 dr_pri = neigh->dr_priority;
103 RFC 4601: 4.3.2. DR Election
105 A router's idea of the current DR on an interface can change when a
106 PIM Hello message is received, when a neighbor times out, or when a
107 router's own DR Priority changes.
109 int pim_if_dr_election(struct interface *ifp)
111 struct pim_interface *pim_ifp = ifp->info;
112 struct in_addr old_dr_addr;
114 ++pim_ifp->pim_dr_election_count;
116 old_dr_addr = pim_ifp->pim_dr_addr;
118 if (pim_ifp->pim_dr_num_nondrpri_neighbors) {
119 dr_election_by_addr(ifp);
122 dr_election_by_pri(ifp);
126 if (old_dr_addr.s_addr != pim_ifp->pim_dr_addr.s_addr) {
128 if (PIM_DEBUG_PIM_EVENTS) {
129 char dr_old_str[100];
130 char dr_new_str[100];
131 pim_inet4_dump("<old_dr?>", old_dr_addr, dr_old_str, sizeof(dr_old_str));
132 pim_inet4_dump("<new_dr?>", pim_ifp->pim_dr_addr, dr_new_str, sizeof(dr_new_str));
133 zlog_debug("%s: DR was %s now is %s on interface %s",
135 dr_old_str, dr_new_str, ifp->name);
138 pim_ifp->pim_dr_election_last = pim_time_monotonic_sec(); /* timestamp */
139 ++pim_ifp->pim_dr_election_changes;
140 pim_if_update_join_desired(pim_ifp);
141 pim_if_update_could_assert(ifp);
142 pim_if_update_assert_tracking_desired(ifp);
149 static void update_dr_priority(struct pim_neighbor *neigh,
150 pim_hello_options hello_options,
151 uint32_t dr_priority)
153 pim_hello_options will_set_pri; /* boolean */
154 pim_hello_options bit_flip; /* boolean */
155 pim_hello_options pri_change; /* boolean */
157 will_set_pri = PIM_OPTION_IS_SET(hello_options,
158 PIM_OPTION_MASK_DR_PRIORITY);
163 PIM_OPTION_IS_SET(neigh->hello_options, PIM_OPTION_MASK_DR_PRIORITY)
167 struct pim_interface *pim_ifp = neigh->interface->info;
169 /* update num. of neighbors without dr_pri */
172 --pim_ifp->pim_dr_num_nondrpri_neighbors;
175 ++pim_ifp->pim_dr_num_nondrpri_neighbors;
183 (neigh->dr_priority != dr_priority)
187 neigh->dr_priority = dr_priority;
190 neigh->dr_priority = 0; /* cosmetic unset */
195 RFC 4601: 4.3.2. DR Election
197 A router's idea of the current DR on an interface can change when a
198 PIM Hello message is received, when a neighbor times out, or when a
199 router's own DR Priority changes.
201 pim_if_dr_election(neigh->interface); // router's own DR Priority changes
205 static int on_neighbor_timer(struct thread *t)
207 struct pim_neighbor *neigh;
208 struct interface *ifp;
212 neigh = THREAD_ARG(t);
215 ifp = neigh->interface;
217 if (PIM_DEBUG_PIM_TRACE) {
219 pim_inet4_dump("<src?>", neigh->source_addr, src_str, sizeof(src_str));
220 zlog_debug("Expired %d sec holdtime for neighbor %s on interface %s",
221 neigh->holdtime, src_str, ifp->name);
224 neigh->t_expire_timer = 0;
226 snprintf(msg, sizeof(msg), "%d-sec holdtime expired", neigh->holdtime);
227 pim_neighbor_delete(ifp, neigh, msg);
230 RFC 4601: 4.3.2. DR Election
232 A router's idea of the current DR on an interface can change when a
233 PIM Hello message is received, when a neighbor times out, or when a
234 router's own DR Priority changes.
236 pim_if_dr_election(ifp); // neighbor times out
241 static void neighbor_timer_off(struct pim_neighbor *neigh)
243 if (PIM_DEBUG_PIM_TRACE) {
244 if (neigh->t_expire_timer) {
246 pim_inet4_dump("<src?>", neigh->source_addr, src_str, sizeof(src_str));
247 zlog_debug("%s: cancelling timer for neighbor %s on %s",
249 src_str, neigh->interface->name);
252 THREAD_OFF(neigh->t_expire_timer);
253 zassert(!neigh->t_expire_timer);
256 void pim_neighbor_timer_reset(struct pim_neighbor *neigh, uint16_t holdtime)
258 neigh->holdtime = holdtime;
260 neighbor_timer_off(neigh);
263 0xFFFF is request for no holdtime
265 if (neigh->holdtime == 0xFFFF) {
269 if (PIM_DEBUG_PIM_TRACE) {
271 pim_inet4_dump("<src?>", neigh->source_addr, src_str, sizeof(src_str));
272 zlog_debug("%s: starting %u sec timer for neighbor %s on %s",
274 neigh->holdtime, src_str, neigh->interface->name);
277 THREAD_TIMER_ON(master, neigh->t_expire_timer,
279 neigh, neigh->holdtime);
282 static struct pim_neighbor *pim_neighbor_new(struct interface *ifp,
283 struct in_addr source_addr,
284 pim_hello_options hello_options,
286 uint16_t propagation_delay,
287 uint16_t override_interval,
288 uint32_t dr_priority,
289 uint32_t generation_id,
290 struct list *addr_list)
292 struct pim_interface *pim_ifp;
293 struct pim_neighbor *neigh;
300 neigh = XMALLOC(MTYPE_PIM_NEIGHBOR, sizeof(*neigh));
302 zlog_err("%s: PIM XMALLOC(%zu) failure",
303 __PRETTY_FUNCTION__, sizeof(*neigh));
307 neigh->creation = pim_time_monotonic_sec();
308 neigh->source_addr = source_addr;
309 neigh->hello_options = hello_options;
310 neigh->propagation_delay_msec = propagation_delay;
311 neigh->override_interval_msec = override_interval;
312 neigh->dr_priority = dr_priority;
313 neigh->generation_id = generation_id;
314 neigh->prefix_list = addr_list;
315 neigh->t_expire_timer = 0;
316 neigh->interface = ifp;
318 pim_neighbor_timer_reset(neigh, holdtime);
320 pim_inet4_dump("<src?>", source_addr, src_str, sizeof(src_str));
322 if (PIM_DEBUG_PIM_EVENTS) {
323 zlog_debug("%s: creating PIM neighbor %s on interface %s",
328 zlog_info("PIM NEIGHBOR UP: neighbor %s on interface %s",
331 if (neigh->propagation_delay_msec > pim_ifp->pim_neighbors_highest_propagation_delay_msec) {
332 pim_ifp->pim_neighbors_highest_propagation_delay_msec = neigh->propagation_delay_msec;
334 if (neigh->override_interval_msec > pim_ifp->pim_neighbors_highest_override_interval_msec) {
335 pim_ifp->pim_neighbors_highest_override_interval_msec = neigh->override_interval_msec;
338 if (!PIM_OPTION_IS_SET(neigh->hello_options,
339 PIM_OPTION_MASK_LAN_PRUNE_DELAY)) {
340 /* update num. of neighbors without hello option lan_delay */
341 ++pim_ifp->pim_number_of_nonlandelay_neighbors;
344 if (!PIM_OPTION_IS_SET(neigh->hello_options,
345 PIM_OPTION_MASK_DR_PRIORITY)) {
346 /* update num. of neighbors without hello option dr_pri */
347 ++pim_ifp->pim_dr_num_nondrpri_neighbors;
353 static void delete_prefix_list(struct pim_neighbor *neigh)
355 if (neigh->prefix_list) {
357 #ifdef DUMP_PREFIX_LIST
358 struct listnode *p_node;
361 int list_size = neigh->prefix_list ? (int) listcount(neigh->prefix_list) : -1;
363 for (ALL_LIST_ELEMENTS_RO(neigh->prefix_list, p_node, p)) {
364 pim_inet4_dump("<addr?>", p->u.prefix4, addr_str, sizeof(addr_str));
365 zlog_debug("%s: DUMP_PREFIX_LIST neigh=%x prefix_list=%x prefix=%x addr=%s [%d/%d]",
367 (unsigned) neigh, (unsigned) neigh->prefix_list, (unsigned) p,
368 addr_str, i, list_size);
373 list_delete(neigh->prefix_list);
374 neigh->prefix_list = 0;
378 void pim_neighbor_free(struct pim_neighbor *neigh)
380 zassert(!neigh->t_expire_timer);
382 delete_prefix_list(neigh);
384 XFREE(MTYPE_PIM_NEIGHBOR, neigh);
387 struct pim_neighbor *pim_neighbor_find(struct interface *ifp,
388 struct in_addr source_addr)
390 struct pim_interface *pim_ifp;
391 struct listnode *node;
392 struct pim_neighbor *neigh;
397 for (ALL_LIST_ELEMENTS_RO(pim_ifp->pim_neighbor_list, node, neigh)) {
398 if (source_addr.s_addr == neigh->source_addr.s_addr) {
406 struct pim_neighbor *pim_neighbor_add(struct interface *ifp,
407 struct in_addr source_addr,
408 pim_hello_options hello_options,
410 uint16_t propagation_delay,
411 uint16_t override_interval,
412 uint32_t dr_priority,
413 uint32_t generation_id,
414 struct list *addr_list)
416 struct pim_interface *pim_ifp;
417 struct pim_neighbor *neigh;
419 neigh = pim_neighbor_new(ifp, source_addr,
434 listnode_add(pim_ifp->pim_neighbor_list, neigh);
437 RFC 4601: 4.3.2. DR Election
439 A router's idea of the current DR on an interface can change when a
440 PIM Hello message is received, when a neighbor times out, or when a
441 router's own DR Priority changes.
443 pim_if_dr_election(neigh->interface); // new neighbor -- should not trigger dr election...
446 RFC 4601: 4.3.1. Sending Hello Messages
448 To allow new or rebooting routers to learn of PIM neighbors quickly,
449 when a Hello message is received from a new neighbor, or a Hello
450 message with a new GenID is received from an existing neighbor, a
451 new Hello message should be sent on this interface after a
452 randomized delay between 0 and Triggered_Hello_Delay.
454 pim_hello_restart_triggered(neigh->interface);
460 find_neighbors_next_highest_propagation_delay_msec(struct interface *ifp,
461 struct pim_neighbor *highest_neigh)
463 struct pim_interface *pim_ifp;
464 struct listnode *neigh_node;
465 struct pim_neighbor *neigh;
466 uint16_t next_highest_delay_msec;
471 next_highest_delay_msec = pim_ifp->pim_propagation_delay_msec;
473 for (ALL_LIST_ELEMENTS_RO(pim_ifp->pim_neighbor_list, neigh_node, neigh)) {
474 if (neigh == highest_neigh)
476 if (neigh->propagation_delay_msec > next_highest_delay_msec)
477 next_highest_delay_msec = neigh->propagation_delay_msec;
480 return next_highest_delay_msec;
484 find_neighbors_next_highest_override_interval_msec(struct interface *ifp,
485 struct pim_neighbor *highest_neigh)
487 struct pim_interface *pim_ifp;
488 struct listnode *neigh_node;
489 struct pim_neighbor *neigh;
490 uint16_t next_highest_interval_msec;
495 next_highest_interval_msec = pim_ifp->pim_override_interval_msec;
497 for (ALL_LIST_ELEMENTS_RO(pim_ifp->pim_neighbor_list, neigh_node, neigh)) {
498 if (neigh == highest_neigh)
500 if (neigh->override_interval_msec > next_highest_interval_msec)
501 next_highest_interval_msec = neigh->override_interval_msec;
504 return next_highest_interval_msec;
507 void pim_neighbor_delete(struct interface *ifp,
508 struct pim_neighbor *neigh,
509 const char *delete_message)
511 struct pim_interface *pim_ifp;
517 pim_inet4_dump("<src?>", neigh->source_addr, src_str, sizeof(src_str));
518 zlog_info("PIM NEIGHBOR DOWN: neighbor %s on interface %s: %s",
519 src_str, ifp->name, delete_message);
521 neighbor_timer_off(neigh);
523 pim_if_assert_on_neighbor_down(ifp, neigh->source_addr);
525 if (!PIM_OPTION_IS_SET(neigh->hello_options,
526 PIM_OPTION_MASK_LAN_PRUNE_DELAY)) {
527 /* update num. of neighbors without hello option lan_delay */
529 --pim_ifp->pim_number_of_nonlandelay_neighbors;
532 if (!PIM_OPTION_IS_SET(neigh->hello_options,
533 PIM_OPTION_MASK_DR_PRIORITY)) {
534 /* update num. of neighbors without dr_pri */
536 --pim_ifp->pim_dr_num_nondrpri_neighbors;
539 zassert(neigh->propagation_delay_msec <= pim_ifp->pim_neighbors_highest_propagation_delay_msec);
540 zassert(neigh->override_interval_msec <= pim_ifp->pim_neighbors_highest_override_interval_msec);
542 if (pim_if_lan_delay_enabled(ifp)) {
544 /* will delete a neighbor with highest propagation delay? */
545 if (neigh->propagation_delay_msec == pim_ifp->pim_neighbors_highest_propagation_delay_msec) {
546 /* then find the next highest propagation delay */
547 pim_ifp->pim_neighbors_highest_propagation_delay_msec =
548 find_neighbors_next_highest_propagation_delay_msec(ifp, neigh);
551 /* will delete a neighbor with highest override interval? */
552 if (neigh->override_interval_msec == pim_ifp->pim_neighbors_highest_override_interval_msec) {
553 /* then find the next highest propagation delay */
554 pim_ifp->pim_neighbors_highest_override_interval_msec =
555 find_neighbors_next_highest_override_interval_msec(ifp, neigh);
559 if (PIM_DEBUG_PIM_TRACE) {
560 zlog_debug("%s: deleting PIM neighbor %s on interface %s",
565 listnode_delete(pim_ifp->pim_neighbor_list, neigh);
567 pim_neighbor_free(neigh);
570 void pim_neighbor_delete_all(struct interface *ifp,
571 const char *delete_message)
573 struct pim_interface *pim_ifp;
574 struct listnode *neigh_node;
575 struct listnode *neigh_nextnode;
576 struct pim_neighbor *neigh;
581 for (ALL_LIST_ELEMENTS(pim_ifp->pim_neighbor_list, neigh_node,
582 neigh_nextnode, neigh)) {
583 pim_neighbor_delete(ifp, neigh, delete_message);
587 struct prefix *pim_neighbor_find_secondary(struct pim_neighbor *neigh,
590 struct listnode *node;
593 if (!neigh->prefix_list)
596 for (ALL_LIST_ELEMENTS_RO(neigh->prefix_list, node, p)) {
597 if (p->family == AF_INET) {
598 if (addr.s_addr == p->u.prefix4.s_addr) {
608 RFC 4601: 4.3.4. Maintaining Secondary Address Lists
610 All the advertised secondary addresses in received Hello messages
611 must be checked against those previously advertised by all other
612 PIM neighbors on that interface. If there is a conflict and the
613 same secondary address was previously advertised by another
614 neighbor, then only the most recently received mapping MUST be
615 maintained, and an error message SHOULD be logged to the
616 administrator in a rate-limited manner.
618 static void delete_from_neigh_addr(struct interface *ifp,
619 struct list *addr_list,
620 struct in_addr neigh_addr)
622 struct listnode *addr_node;
624 struct pim_interface *pim_ifp;
632 Scan secondary address list
634 for (ALL_LIST_ELEMENTS_RO(addr_list, addr_node,
636 struct listnode *neigh_node;
637 struct pim_neighbor *neigh;
639 if (addr->family != AF_INET)
645 for (ALL_LIST_ELEMENTS_RO(pim_ifp->pim_neighbor_list, neigh_node,
648 struct prefix *p = pim_neighbor_find_secondary(neigh, addr->u.prefix4);
651 char this_neigh_str[100];
652 char other_neigh_str[100];
654 pim_inet4_dump("<addr?>", addr->u.prefix4, addr_str, sizeof(addr_str));
655 pim_inet4_dump("<neigh1?>", neigh_addr, this_neigh_str, sizeof(this_neigh_str));
656 pim_inet4_dump("<neigh2?>", neigh->source_addr, other_neigh_str, sizeof(other_neigh_str));
658 zlog_info("secondary addr %s recvd from neigh %s deleted from neigh %s on %s",
659 addr_str, this_neigh_str, other_neigh_str, ifp->name);
661 listnode_delete(neigh->prefix_list, p);
666 } /* scan neighbors */
668 } /* scan addr list */
672 void pim_neighbor_update(struct pim_neighbor *neigh,
673 pim_hello_options hello_options,
675 uint32_t dr_priority,
676 struct list *addr_list)
678 struct pim_interface *pim_ifp = neigh->interface->info;
680 /* Received holdtime ? */
681 if (PIM_OPTION_IS_SET(hello_options, PIM_OPTION_MASK_HOLDTIME)) {
682 pim_neighbor_timer_reset(neigh, holdtime);
685 pim_neighbor_timer_reset(neigh, PIM_IF_DEFAULT_HOLDTIME(pim_ifp));
688 #ifdef DUMP_PREFIX_LIST
689 zlog_debug("%s: DUMP_PREFIX_LIST old_prefix_list=%x old_size=%d new_prefix_list=%x new_size=%d",
691 (unsigned) neigh->prefix_list,
692 neigh->prefix_list ? (int) listcount(neigh->prefix_list) : -1,
693 (unsigned) addr_list,
694 addr_list ? (int) listcount(addr_list) : -1);
697 if (neigh->prefix_list == addr_list) {
699 zlog_err("%s: internal error: trying to replace same prefix list=%p",
700 __PRETTY_FUNCTION__, (void *) addr_list);
704 /* Delete existing secondary address list */
705 delete_prefix_list(neigh);
709 delete_from_neigh_addr(neigh->interface, addr_list, neigh->source_addr);
712 /* Replace secondary address list */
713 neigh->prefix_list = addr_list;
715 update_dr_priority(neigh,
721 neigh->hello_options = hello_options;