1 // SPDX-License-Identifier: GPL-2.0-or-later
3 * OSPF version 2 Interface State Machine
4 * From RFC2328 [OSPF Version 2]
5 * Copyright (C) 1999, 2000 Toshiaki Takada
17 #include "ospfd/ospfd.h"
18 #include "ospfd/ospf_interface.h"
19 #include "ospfd/ospf_ism.h"
20 #include "ospfd/ospf_asbr.h"
21 #include "ospfd/ospf_lsa.h"
22 #include "ospfd/ospf_lsdb.h"
23 #include "ospfd/ospf_neighbor.h"
24 #include "ospfd/ospf_nsm.h"
25 #include "ospfd/ospf_network.h"
26 #include "ospfd/ospf_dump.h"
27 #include "ospfd/ospf_packet.h"
28 #include "ospfd/ospf_flood.h"
29 #include "ospfd/ospf_abr.h"
31 DEFINE_HOOK(ospf_ism_change
,
32 (struct ospf_interface
* oi
, int state
, int oldstate
),
33 (oi
, state
, oldstate
));
35 /* elect DR and BDR. Refer to RFC2319 section 9.4 */
36 static struct ospf_neighbor
*ospf_dr_election_sub(struct list
*routers
)
38 struct listnode
*node
;
39 struct ospf_neighbor
*nbr
, *max
= NULL
;
41 /* Choose highest router priority.
42 In case of tie, choose highest Router ID. */
43 for (ALL_LIST_ELEMENTS_RO(routers
, node
, nbr
)) {
47 if (max
->priority
< nbr
->priority
)
49 else if (max
->priority
== nbr
->priority
)
50 if (IPV4_ADDR_CMP(&max
->router_id
,
60 static struct ospf_neighbor
*ospf_elect_dr(struct ospf_interface
*oi
,
64 struct listnode
*node
;
65 struct ospf_neighbor
*nbr
, *dr
= NULL
, *bdr
= NULL
;
69 /* Add neighbors to the list. */
70 for (ALL_LIST_ELEMENTS_RO(el_list
, node
, nbr
)) {
71 /* neighbor declared to be DR. */
73 listnode_add(dr_list
, nbr
);
75 /* Preserve neighbor BDR. */
76 if (IPV4_ADDR_SAME(&BDR(oi
), &nbr
->address
.u
.prefix4
))
80 /* Elect Designated Router. */
81 if (listcount(dr_list
) > 0)
82 dr
= ospf_dr_election_sub(dr_list
);
86 /* Set DR to interface. */
88 DR(oi
) = dr
->address
.u
.prefix4
;
92 list_delete(&dr_list
);
97 static struct ospf_neighbor
*ospf_elect_bdr(struct ospf_interface
*oi
,
100 struct list
*bdr_list
, *no_dr_list
;
101 struct listnode
*node
;
102 struct ospf_neighbor
*nbr
, *bdr
= NULL
;
104 bdr_list
= list_new();
105 no_dr_list
= list_new();
107 /* Add neighbors to the list. */
108 for (ALL_LIST_ELEMENTS_RO(el_list
, node
, nbr
)) {
109 /* neighbor declared to be DR. */
113 /* neighbor declared to be BDR. */
115 listnode_add(bdr_list
, nbr
);
117 listnode_add(no_dr_list
, nbr
);
120 /* Elect Backup Designated Router. */
121 if (listcount(bdr_list
) > 0)
122 bdr
= ospf_dr_election_sub(bdr_list
);
124 bdr
= ospf_dr_election_sub(no_dr_list
);
126 /* Set BDR to interface. */
128 BDR(oi
) = bdr
->address
.u
.prefix4
;
132 list_delete(&bdr_list
);
133 list_delete(&no_dr_list
);
138 static int ospf_ism_state(struct ospf_interface
*oi
)
140 if (IPV4_ADDR_SAME(&DR(oi
), &oi
->address
->u
.prefix4
))
142 else if (IPV4_ADDR_SAME(&BDR(oi
), &oi
->address
->u
.prefix4
))
148 static void ospf_dr_eligible_routers(struct route_table
*nbrs
,
149 struct list
*el_list
)
151 struct route_node
*rn
;
152 struct ospf_neighbor
*nbr
;
154 for (rn
= route_top(nbrs
); rn
; rn
= route_next(rn
))
155 if ((nbr
= rn
->info
) != NULL
)
156 /* Ignore 0.0.0.0 node*/
157 if (nbr
->router_id
.s_addr
!= INADDR_ANY
)
158 /* Is neighbor eligible? */
159 if (nbr
->priority
> 0)
160 /* Is neighbor upper 2-Way? */
161 if (nbr
->state
>= NSM_TwoWay
)
162 listnode_add(el_list
, nbr
);
165 /* Generate AdjOK? NSM event. */
166 static void ospf_dr_change(struct ospf
*ospf
, struct route_table
*nbrs
)
168 struct route_node
*rn
;
169 struct ospf_neighbor
*nbr
;
171 for (rn
= route_top(nbrs
); rn
; rn
= route_next(rn
)) {
178 * Ignore 0.0.0.0 node
182 if (nbr
->router_id
.s_addr
!= INADDR_ANY
183 && nbr
->state
>= NSM_TwoWay
184 && !IPV4_ADDR_SAME(&nbr
->router_id
, &ospf
->router_id
))
185 OSPF_NSM_EVENT_SCHEDULE(nbr
, NSM_AdjOK
);
189 int ospf_dr_election(struct ospf_interface
*oi
)
191 struct in_addr old_dr
, old_bdr
;
192 int old_state
, new_state
;
193 struct list
*el_list
;
195 /* backup current values. */
198 old_state
= oi
->state
;
200 el_list
= list_new();
202 /* List eligible routers. */
203 ospf_dr_eligible_routers(oi
->nbrs
, el_list
);
205 /* First election of DR and BDR. */
206 ospf_elect_bdr(oi
, el_list
);
207 ospf_elect_dr(oi
, el_list
);
209 new_state
= ospf_ism_state(oi
);
211 if (IS_DEBUG_OSPF(ism
, ISM_STATUS
)) {
212 zlog_debug("DR-Election[1st]: Backup %pI4", &BDR(oi
));
213 zlog_debug("DR-Election[1st]: DR %pI4", &DR(oi
));
216 if (new_state
!= old_state
217 && !(new_state
== ISM_DROther
&& old_state
< ISM_DROther
)) {
218 ospf_elect_bdr(oi
, el_list
);
219 ospf_elect_dr(oi
, el_list
);
221 new_state
= ospf_ism_state(oi
);
223 if (IS_DEBUG_OSPF(ism
, ISM_STATUS
)) {
224 zlog_debug("DR-Election[2nd]: Backup %pI4", &BDR(oi
));
225 zlog_debug("DR-Election[2nd]: DR %pI4", &DR(oi
));
229 list_delete(&el_list
);
231 /* if DR or BDR changes, cause AdjOK? neighbor event. */
232 if (!IPV4_ADDR_SAME(&old_dr
, &DR(oi
))
233 || !IPV4_ADDR_SAME(&old_bdr
, &BDR(oi
)))
234 ospf_dr_change(oi
->ospf
, oi
->nbrs
);
240 void ospf_hello_timer(struct event
*thread
)
242 struct ospf_interface
*oi
;
244 oi
= EVENT_ARG(thread
);
247 if (IS_DEBUG_OSPF(ism
, ISM_TIMERS
))
248 zlog_debug("ISM[%s]: Timer (Hello timer expire)", IF_NAME(oi
));
250 /* Sending hello packet. */
253 /* Hello timer set. */
254 OSPF_HELLO_TIMER_ON(oi
);
257 static void ospf_wait_timer(struct event
*thread
)
259 struct ospf_interface
*oi
;
261 oi
= EVENT_ARG(thread
);
264 if (IS_DEBUG_OSPF(ism
, ISM_TIMERS
))
265 zlog_debug("ISM[%s]: Timer (Wait timer expire)", IF_NAME(oi
));
267 OSPF_ISM_EVENT_SCHEDULE(oi
, ISM_WaitTimer
);
270 /* Hook function called after ospf ISM event is occurred. And vty's
271 network command invoke this function after making interface
273 static void ism_timer_set(struct ospf_interface
*oi
)
277 /* First entry point of ospf interface state machine. In this
279 interface parameters must be set to initial values, and
282 EVENT_OFF(oi
->t_hello
);
283 EVENT_OFF(oi
->t_wait
);
284 EVENT_OFF(oi
->t_ls_ack
);
287 /* In this state, the interface may be looped back and will be
288 unavailable for regular data traffic. */
289 EVENT_OFF(oi
->t_hello
);
290 EVENT_OFF(oi
->t_wait
);
291 EVENT_OFF(oi
->t_ls_ack
);
294 /* The router is trying to determine the identity of DRouter and
295 BDRouter. The router begin to receive and send Hello Packets.
297 /* send first hello immediately */
298 OSPF_ISM_TIMER_MSEC_ON(oi
->t_hello
, ospf_hello_timer
, 1);
299 OSPF_ISM_TIMER_ON(oi
->t_wait
, ospf_wait_timer
,
300 OSPF_IF_PARAM(oi
, v_wait
));
301 EVENT_OFF(oi
->t_ls_ack
);
303 case ISM_PointToPoint
:
304 /* The interface connects to a physical Point-to-point network
306 virtual link. The router attempts to form an adjacency with
307 neighboring router. Hello packets are also sent. */
308 /* send first hello immediately */
309 OSPF_ISM_TIMER_MSEC_ON(oi
->t_hello
, ospf_hello_timer
, 1);
310 EVENT_OFF(oi
->t_wait
);
311 OSPF_ISM_TIMER_ON(oi
->t_ls_ack
, ospf_ls_ack_timer
,
315 /* The network type of the interface is broadcast or NBMA
317 and the router itself is neither Designated Router nor
318 Backup Designated Router. */
319 OSPF_HELLO_TIMER_ON(oi
);
320 EVENT_OFF(oi
->t_wait
);
321 OSPF_ISM_TIMER_ON(oi
->t_ls_ack
, ospf_ls_ack_timer
,
325 /* The network type of the interface is broadcast os NBMA
327 and the router is Backup Designated Router. */
328 OSPF_HELLO_TIMER_ON(oi
);
329 EVENT_OFF(oi
->t_wait
);
330 OSPF_ISM_TIMER_ON(oi
->t_ls_ack
, ospf_ls_ack_timer
,
334 /* The network type of the interface is broadcast or NBMA
336 and the router is Designated Router. */
337 OSPF_HELLO_TIMER_ON(oi
);
338 EVENT_OFF(oi
->t_wait
);
339 OSPF_ISM_TIMER_ON(oi
->t_ls_ack
, ospf_ls_ack_timer
,
345 static int ism_interface_up(struct ospf_interface
*oi
)
349 /* if network type is point-to-point, Point-to-MultiPoint or virtual
351 the state transitions to Point-to-Point. */
352 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
353 || oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
354 || oi
->type
== OSPF_IFTYPE_VIRTUALLINK
)
355 next_state
= ISM_PointToPoint
;
356 /* Else if the router is not eligible to DR, the state transitions to
358 else if (PRIORITY(oi
) == 0) /* router is eligible? */
359 next_state
= ISM_DROther
;
361 /* Otherwise, the state transitions to Waiting. */
362 next_state
= ISM_Waiting
;
364 if (oi
->type
== OSPF_IFTYPE_NBMA
)
365 ospf_nbr_nbma_if_update(oi
->ospf
, oi
);
367 /* ospf_ism_event (t); */
371 static int ism_loop_ind(struct ospf_interface
*oi
)
373 /* call ism_interface_down. */
374 /* ret = ism_interface_down (oi); */
379 /* Interface down event handler. */
380 static int ism_interface_down(struct ospf_interface
*oi
)
387 static int ism_backup_seen(struct ospf_interface
*oi
)
389 return ospf_dr_election(oi
);
392 static int ism_wait_timer(struct ospf_interface
*oi
)
394 return ospf_dr_election(oi
);
397 static int ism_neighbor_change(struct ospf_interface
*oi
)
399 return ospf_dr_election(oi
);
402 static int ism_ignore(struct ospf_interface
*oi
)
404 if (IS_DEBUG_OSPF(ism
, ISM_EVENTS
))
405 zlog_debug("ISM[%s]: ism_ignore called", IF_NAME(oi
));
410 /* Interface State Machine */
412 int (*func
)(struct ospf_interface
*);
414 } ISM
[OSPF_ISM_STATE_MAX
][OSPF_ISM_EVENT_MAX
] = {
416 /* DependUpon: dummy state. */
417 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
418 {ism_ignore
, ISM_DependUpon
}, /* InterfaceUp */
419 {ism_ignore
, ISM_DependUpon
}, /* WaitTimer */
420 {ism_ignore
, ISM_DependUpon
}, /* BackupSeen */
421 {ism_ignore
, ISM_DependUpon
}, /* NeighborChange */
422 {ism_ignore
, ISM_DependUpon
}, /* LoopInd */
423 {ism_ignore
, ISM_DependUpon
}, /* UnloopInd */
424 {ism_ignore
, ISM_DependUpon
}, /* InterfaceDown */
428 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
429 {ism_interface_up
, ISM_DependUpon
}, /* InterfaceUp */
430 {ism_ignore
, ISM_Down
}, /* WaitTimer */
431 {ism_ignore
, ISM_Down
}, /* BackupSeen */
432 {ism_ignore
, ISM_Down
}, /* NeighborChange */
433 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
434 {ism_ignore
, ISM_Down
}, /* UnloopInd */
435 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
439 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
440 {ism_ignore
, ISM_Loopback
}, /* InterfaceUp */
441 {ism_ignore
, ISM_Loopback
}, /* WaitTimer */
442 {ism_ignore
, ISM_Loopback
}, /* BackupSeen */
443 {ism_ignore
, ISM_Loopback
}, /* NeighborChange */
444 {ism_ignore
, ISM_Loopback
}, /* LoopInd */
445 {ism_ignore
, ISM_Down
}, /* UnloopInd */
446 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
450 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
451 {ism_ignore
, ISM_Waiting
}, /* InterfaceUp */
452 {ism_wait_timer
, ISM_DependUpon
}, /* WaitTimer */
453 {ism_backup_seen
, ISM_DependUpon
}, /* BackupSeen */
454 {ism_ignore
, ISM_Waiting
}, /* NeighborChange */
455 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
456 {ism_ignore
, ISM_Waiting
}, /* UnloopInd */
457 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
460 /* Point-to-Point: */
461 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
462 {ism_ignore
, ISM_PointToPoint
}, /* InterfaceUp */
463 {ism_ignore
, ISM_PointToPoint
}, /* WaitTimer */
464 {ism_ignore
, ISM_PointToPoint
}, /* BackupSeen */
465 {ism_ignore
, ISM_PointToPoint
}, /* NeighborChange */
466 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
467 {ism_ignore
, ISM_PointToPoint
}, /* UnloopInd */
468 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
472 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
473 {ism_ignore
, ISM_DROther
}, /* InterfaceUp */
474 {ism_ignore
, ISM_DROther
}, /* WaitTimer */
475 {ism_ignore
, ISM_DROther
}, /* BackupSeen */
476 {ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
477 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
478 {ism_ignore
, ISM_DROther
}, /* UnloopInd */
479 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
483 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
484 {ism_ignore
, ISM_Backup
}, /* InterfaceUp */
485 {ism_ignore
, ISM_Backup
}, /* WaitTimer */
486 {ism_ignore
, ISM_Backup
}, /* BackupSeen */
487 {ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
488 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
489 {ism_ignore
, ISM_Backup
}, /* UnloopInd */
490 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
494 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
495 {ism_ignore
, ISM_DR
}, /* InterfaceUp */
496 {ism_ignore
, ISM_DR
}, /* WaitTimer */
497 {ism_ignore
, ISM_DR
}, /* BackupSeen */
498 {ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
499 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
500 {ism_ignore
, ISM_DR
}, /* UnloopInd */
501 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
505 static const char *const ospf_ism_event_str
[] = {
506 "NoEvent", "InterfaceUp", "WaitTimer", "BackupSeen",
507 "NeighborChange", "LoopInd", "UnLoopInd", "InterfaceDown",
510 static void ism_change_state(struct ospf_interface
*oi
, int state
)
513 struct ospf_lsa
*lsa
;
515 /* Logging change of state. */
516 if (IS_DEBUG_OSPF(ism
, ISM_STATUS
))
517 zlog_debug("ISM[%s]: State change %s -> %s", IF_NAME(oi
),
518 lookup_msg(ospf_ism_state_msg
, oi
->state
, NULL
),
519 lookup_msg(ospf_ism_state_msg
, state
, NULL
));
521 old_state
= oi
->state
;
525 hook_call(ospf_ism_change
, oi
, state
, old_state
);
527 /* Set multicast memberships appropriately for new state. */
528 ospf_if_set_multicast(oi
);
530 if (old_state
== ISM_Down
|| state
== ISM_Down
)
531 ospf_check_abr_status(oi
->ospf
);
533 /* Originate router-LSA. */
534 if (state
== ISM_Down
) {
535 if (oi
->area
->act_ints
> 0)
536 oi
->area
->act_ints
--;
537 } else if (old_state
== ISM_Down
)
538 oi
->area
->act_ints
++;
540 /* schedule router-LSA originate. */
541 ospf_router_lsa_update_area(oi
->area
);
543 /* Originate network-LSA. */
544 if (old_state
!= ISM_DR
&& state
== ISM_DR
)
545 ospf_network_lsa_update(oi
);
546 else if (old_state
== ISM_DR
&& state
!= ISM_DR
) {
547 /* Free self originated network LSA. */
548 lsa
= oi
->network_lsa_self
;
550 ospf_lsa_flush_area(lsa
, oi
->area
);
552 ospf_lsa_unlock(&oi
->network_lsa_self
);
553 oi
->network_lsa_self
= NULL
;
556 ospf_opaque_ism_change(oi
, old_state
);
558 /* Check area border status. */
559 ospf_check_abr_status(oi
->ospf
);
562 /* Execute ISM event process. */
563 void ospf_ism_event(struct event
*thread
)
567 struct ospf_interface
*oi
;
569 oi
= EVENT_ARG(thread
);
570 event
= EVENT_VAL(thread
);
573 next_state
= (*(ISM
[oi
->state
][event
].func
))(oi
);
576 next_state
= ISM
[oi
->state
][event
].next_state
;
578 if (IS_DEBUG_OSPF(ism
, ISM_EVENTS
))
579 zlog_debug("ISM[%s]: %s (%s)", IF_NAME(oi
),
580 lookup_msg(ospf_ism_state_msg
, oi
->state
, NULL
),
581 ospf_ism_event_str
[event
]);
583 /* If state is changed. */
584 if (next_state
!= oi
->state
)
585 ism_change_state(oi
, next_state
);
587 /* Make sure timer is set. */