2 * OSPF version 2 Interface State Machine
3 * From RFC2328 [OSPF Version 2]
4 * Copyright (C) 1999, 2000 Toshiaki Takada
6 * This file is part of GNU Zebra.
8 * GNU Zebra is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License as published by the
10 * Free Software Foundation; either version 2, or (at your option) any
13 * GNU Zebra is distributed in the hope that it will be useful, but
14 * WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * General Public License for more details.
18 * You should have received a copy of the GNU General Public License along
19 * with this program; see the file COPYING; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
32 #include "ospfd/ospfd.h"
33 #include "ospfd/ospf_interface.h"
34 #include "ospfd/ospf_ism.h"
35 #include "ospfd/ospf_asbr.h"
36 #include "ospfd/ospf_lsa.h"
37 #include "ospfd/ospf_lsdb.h"
38 #include "ospfd/ospf_neighbor.h"
39 #include "ospfd/ospf_nsm.h"
40 #include "ospfd/ospf_network.h"
41 #include "ospfd/ospf_dump.h"
42 #include "ospfd/ospf_packet.h"
43 #include "ospfd/ospf_flood.h"
44 #include "ospfd/ospf_abr.h"
46 DEFINE_HOOK(ospf_ism_change
,
47 (struct ospf_interface
* oi
, int state
, int oldstate
),
48 (oi
, state
, oldstate
))
50 /* elect DR and BDR. Refer to RFC2319 section 9.4 */
51 static struct ospf_neighbor
*ospf_dr_election_sub(struct list
*routers
)
53 struct listnode
*node
;
54 struct ospf_neighbor
*nbr
, *max
= NULL
;
56 /* Choose highest router priority.
57 In case of tie, choose highest Router ID. */
58 for (ALL_LIST_ELEMENTS_RO(routers
, node
, nbr
)) {
62 if (max
->priority
< nbr
->priority
)
64 else if (max
->priority
== nbr
->priority
)
65 if (IPV4_ADDR_CMP(&max
->router_id
,
75 static struct ospf_neighbor
*ospf_elect_dr(struct ospf_interface
*oi
,
79 struct listnode
*node
;
80 struct ospf_neighbor
*nbr
, *dr
= NULL
, *bdr
= NULL
;
84 /* Add neighbors to the list. */
85 for (ALL_LIST_ELEMENTS_RO(el_list
, node
, nbr
)) {
86 /* neighbor declared to be DR. */
88 listnode_add(dr_list
, nbr
);
90 /* Preserve neighbor BDR. */
91 if (IPV4_ADDR_SAME(&BDR(oi
), &nbr
->address
.u
.prefix4
))
95 /* Elect Designated Router. */
96 if (listcount(dr_list
) > 0)
97 dr
= ospf_dr_election_sub(dr_list
);
101 /* Set DR to interface. */
103 DR(oi
) = dr
->address
.u
.prefix4
;
107 list_delete_and_null(&dr_list
);
112 static struct ospf_neighbor
*ospf_elect_bdr(struct ospf_interface
*oi
,
113 struct list
*el_list
)
115 struct list
*bdr_list
, *no_dr_list
;
116 struct listnode
*node
;
117 struct ospf_neighbor
*nbr
, *bdr
= NULL
;
119 bdr_list
= list_new();
120 no_dr_list
= list_new();
122 /* Add neighbors to the list. */
123 for (ALL_LIST_ELEMENTS_RO(el_list
, node
, nbr
)) {
124 /* neighbor declared to be DR. */
128 /* neighbor declared to be BDR. */
130 listnode_add(bdr_list
, nbr
);
132 listnode_add(no_dr_list
, nbr
);
135 /* Elect Backup Designated Router. */
136 if (listcount(bdr_list
) > 0)
137 bdr
= ospf_dr_election_sub(bdr_list
);
139 bdr
= ospf_dr_election_sub(no_dr_list
);
141 /* Set BDR to interface. */
143 BDR(oi
) = bdr
->address
.u
.prefix4
;
147 list_delete_and_null(&bdr_list
);
148 list_delete_and_null(&no_dr_list
);
153 static int ospf_ism_state(struct ospf_interface
*oi
)
155 if (IPV4_ADDR_SAME(&DR(oi
), &oi
->address
->u
.prefix4
))
157 else if (IPV4_ADDR_SAME(&BDR(oi
), &oi
->address
->u
.prefix4
))
163 static void ospf_dr_eligible_routers(struct route_table
*nbrs
,
164 struct list
*el_list
)
166 struct route_node
*rn
;
167 struct ospf_neighbor
*nbr
;
169 for (rn
= route_top(nbrs
); rn
; rn
= route_next(rn
))
170 if ((nbr
= rn
->info
) != NULL
)
171 /* Ignore 0.0.0.0 node*/
172 if (nbr
->router_id
.s_addr
!= 0)
173 /* Is neighbor eligible? */
174 if (nbr
->priority
> 0)
175 /* Is neighbor upper 2-Way? */
176 if (nbr
->state
>= NSM_TwoWay
)
177 listnode_add(el_list
, nbr
);
180 /* Generate AdjOK? NSM event. */
181 static void ospf_dr_change(struct ospf
*ospf
, struct route_table
*nbrs
)
183 struct route_node
*rn
;
184 struct ospf_neighbor
*nbr
;
186 for (rn
= route_top(nbrs
); rn
; rn
= route_next(rn
))
187 if ((nbr
= rn
->info
) != NULL
)
188 /* Ignore 0.0.0.0 node*/
189 if (nbr
->router_id
.s_addr
!= 0)
190 /* Is neighbor upper 2-Way? */
191 if (nbr
->state
>= NSM_TwoWay
)
193 if (!IPV4_ADDR_SAME(&nbr
->router_id
,
195 OSPF_NSM_EVENT_SCHEDULE(
199 static int ospf_dr_election(struct ospf_interface
*oi
)
201 struct in_addr old_dr
, old_bdr
;
202 int old_state
, new_state
;
203 struct list
*el_list
;
205 /* backup current values. */
208 old_state
= oi
->state
;
210 el_list
= list_new();
212 /* List eligible routers. */
213 ospf_dr_eligible_routers(oi
->nbrs
, el_list
);
215 /* First election of DR and BDR. */
216 ospf_elect_bdr(oi
, el_list
);
217 ospf_elect_dr(oi
, el_list
);
219 new_state
= ospf_ism_state(oi
);
221 zlog_debug("DR-Election[1st]: Backup %s", inet_ntoa(BDR(oi
)));
222 zlog_debug("DR-Election[1st]: DR %s", inet_ntoa(DR(oi
)));
224 if (new_state
!= old_state
225 && !(new_state
== ISM_DROther
&& old_state
< ISM_DROther
)) {
226 ospf_elect_bdr(oi
, el_list
);
227 ospf_elect_dr(oi
, el_list
);
229 new_state
= ospf_ism_state(oi
);
231 zlog_debug("DR-Election[2nd]: Backup %s", inet_ntoa(BDR(oi
)));
232 zlog_debug("DR-Election[2nd]: DR %s", inet_ntoa(DR(oi
)));
235 list_delete_and_null(&el_list
);
237 /* if DR or BDR changes, cause AdjOK? neighbor event. */
238 if (!IPV4_ADDR_SAME(&old_dr
, &DR(oi
))
239 || !IPV4_ADDR_SAME(&old_bdr
, &BDR(oi
)))
240 ospf_dr_change(oi
->ospf
, oi
->nbrs
);
246 int ospf_hello_timer(struct thread
*thread
)
248 struct ospf_interface
*oi
;
250 oi
= THREAD_ARG(thread
);
253 if (IS_DEBUG_OSPF(ism
, ISM_TIMERS
))
254 zlog_debug("ISM[%s]: Timer (Hello timer expire)", IF_NAME(oi
));
256 /* Sending hello packet. */
259 /* Hello timer set. */
260 OSPF_HELLO_TIMER_ON(oi
);
265 static int ospf_wait_timer(struct thread
*thread
)
267 struct ospf_interface
*oi
;
269 oi
= THREAD_ARG(thread
);
272 if (IS_DEBUG_OSPF(ism
, ISM_TIMERS
))
273 zlog_debug("ISM[%s]: Timer (Wait timer expire)", IF_NAME(oi
));
275 OSPF_ISM_EVENT_SCHEDULE(oi
, ISM_WaitTimer
);
280 /* Hook function called after ospf ISM event is occured. And vty's
281 network command invoke this function after making interface
283 static void ism_timer_set(struct ospf_interface
*oi
)
287 /* First entry point of ospf interface state machine. In this
289 interface parameters must be set to initial values, and
292 OSPF_ISM_TIMER_OFF(oi
->t_hello
);
293 OSPF_ISM_TIMER_OFF(oi
->t_wait
);
294 OSPF_ISM_TIMER_OFF(oi
->t_ls_ack
);
297 /* In this state, the interface may be looped back and will be
298 unavailable for regular data traffic. */
299 OSPF_ISM_TIMER_OFF(oi
->t_hello
);
300 OSPF_ISM_TIMER_OFF(oi
->t_wait
);
301 OSPF_ISM_TIMER_OFF(oi
->t_ls_ack
);
304 /* The router is trying to determine the identity of DRouter and
305 BDRouter. The router begin to receive and send Hello Packets.
307 /* send first hello immediately */
308 OSPF_ISM_TIMER_MSEC_ON(oi
->t_hello
, ospf_hello_timer
, 1);
309 OSPF_ISM_TIMER_ON(oi
->t_wait
, ospf_wait_timer
,
310 OSPF_IF_PARAM(oi
, v_wait
));
311 OSPF_ISM_TIMER_OFF(oi
->t_ls_ack
);
313 case ISM_PointToPoint
:
314 /* The interface connects to a physical Point-to-point network
316 virtual link. The router attempts to form an adjacency with
317 neighboring router. Hello packets are also sent. */
318 /* send first hello immediately */
319 OSPF_ISM_TIMER_MSEC_ON(oi
->t_hello
, ospf_hello_timer
, 1);
320 OSPF_ISM_TIMER_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 or NBMA
327 and the router itself is neither Designated Router nor
328 Backup Designated Router. */
329 OSPF_HELLO_TIMER_ON(oi
);
330 OSPF_ISM_TIMER_OFF(oi
->t_wait
);
331 OSPF_ISM_TIMER_ON(oi
->t_ls_ack
, ospf_ls_ack_timer
,
335 /* The network type of the interface is broadcast os NBMA
337 and the router is Backup Designated Router. */
338 OSPF_HELLO_TIMER_ON(oi
);
339 OSPF_ISM_TIMER_OFF(oi
->t_wait
);
340 OSPF_ISM_TIMER_ON(oi
->t_ls_ack
, ospf_ls_ack_timer
,
344 /* The network type of the interface is broadcast or NBMA
346 and the router is Designated Router. */
347 OSPF_HELLO_TIMER_ON(oi
);
348 OSPF_ISM_TIMER_OFF(oi
->t_wait
);
349 OSPF_ISM_TIMER_ON(oi
->t_ls_ack
, ospf_ls_ack_timer
,
355 static int ism_interface_up(struct ospf_interface
*oi
)
359 /* if network type is point-to-point, Point-to-MultiPoint or virtual
361 the state transitions to Point-to-Point. */
362 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
363 || oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
364 || oi
->type
== OSPF_IFTYPE_VIRTUALLINK
)
365 next_state
= ISM_PointToPoint
;
366 /* Else if the router is not eligible to DR, the state transitions to
368 else if (PRIORITY(oi
) == 0) /* router is eligible? */
369 next_state
= ISM_DROther
;
371 /* Otherwise, the state transitions to Waiting. */
372 next_state
= ISM_Waiting
;
374 if (oi
->type
== OSPF_IFTYPE_NBMA
)
375 ospf_nbr_nbma_if_update(oi
->ospf
, oi
);
377 /* ospf_ism_event (t); */
381 static int ism_loop_ind(struct ospf_interface
*oi
)
385 /* call ism_interface_down. */
386 /* ret = ism_interface_down (oi); */
391 /* Interface down event handler. */
392 static int ism_interface_down(struct ospf_interface
*oi
)
399 static int ism_backup_seen(struct ospf_interface
*oi
)
401 return ospf_dr_election(oi
);
404 static int ism_wait_timer(struct ospf_interface
*oi
)
406 return ospf_dr_election(oi
);
409 static int ism_neighbor_change(struct ospf_interface
*oi
)
411 return ospf_dr_election(oi
);
414 static int ism_ignore(struct ospf_interface
*oi
)
416 if (IS_DEBUG_OSPF(ism
, ISM_EVENTS
))
417 zlog_debug("ISM[%s]: ism_ignore called", IF_NAME(oi
));
422 /* Interface State Machine */
424 int (*func
)(struct ospf_interface
*);
426 } ISM
[OSPF_ISM_STATE_MAX
][OSPF_ISM_EVENT_MAX
] = {
428 /* DependUpon: dummy state. */
429 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
430 {ism_ignore
, ISM_DependUpon
}, /* InterfaceUp */
431 {ism_ignore
, ISM_DependUpon
}, /* WaitTimer */
432 {ism_ignore
, ISM_DependUpon
}, /* BackupSeen */
433 {ism_ignore
, ISM_DependUpon
}, /* NeighborChange */
434 {ism_ignore
, ISM_DependUpon
}, /* LoopInd */
435 {ism_ignore
, ISM_DependUpon
}, /* UnloopInd */
436 {ism_ignore
, ISM_DependUpon
}, /* InterfaceDown */
440 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
441 {ism_interface_up
, ISM_DependUpon
}, /* InterfaceUp */
442 {ism_ignore
, ISM_Down
}, /* WaitTimer */
443 {ism_ignore
, ISM_Down
}, /* BackupSeen */
444 {ism_ignore
, ISM_Down
}, /* NeighborChange */
445 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
446 {ism_ignore
, ISM_Down
}, /* UnloopInd */
447 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
451 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
452 {ism_ignore
, ISM_Loopback
}, /* InterfaceUp */
453 {ism_ignore
, ISM_Loopback
}, /* WaitTimer */
454 {ism_ignore
, ISM_Loopback
}, /* BackupSeen */
455 {ism_ignore
, ISM_Loopback
}, /* NeighborChange */
456 {ism_ignore
, ISM_Loopback
}, /* LoopInd */
457 {ism_ignore
, ISM_Down
}, /* UnloopInd */
458 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
462 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
463 {ism_ignore
, ISM_Waiting
}, /* InterfaceUp */
464 {ism_wait_timer
, ISM_DependUpon
}, /* WaitTimer */
465 {ism_backup_seen
, ISM_DependUpon
}, /* BackupSeen */
466 {ism_ignore
, ISM_Waiting
}, /* NeighborChange */
467 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
468 {ism_ignore
, ISM_Waiting
}, /* UnloopInd */
469 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
472 /* Point-to-Point: */
473 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
474 {ism_ignore
, ISM_PointToPoint
}, /* InterfaceUp */
475 {ism_ignore
, ISM_PointToPoint
}, /* WaitTimer */
476 {ism_ignore
, ISM_PointToPoint
}, /* BackupSeen */
477 {ism_ignore
, ISM_PointToPoint
}, /* NeighborChange */
478 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
479 {ism_ignore
, ISM_PointToPoint
}, /* UnloopInd */
480 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
484 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
485 {ism_ignore
, ISM_DROther
}, /* InterfaceUp */
486 {ism_ignore
, ISM_DROther
}, /* WaitTimer */
487 {ism_ignore
, ISM_DROther
}, /* BackupSeen */
488 {ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
489 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
490 {ism_ignore
, ISM_DROther
}, /* UnloopInd */
491 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
495 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
496 {ism_ignore
, ISM_Backup
}, /* InterfaceUp */
497 {ism_ignore
, ISM_Backup
}, /* WaitTimer */
498 {ism_ignore
, ISM_Backup
}, /* BackupSeen */
499 {ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
500 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
501 {ism_ignore
, ISM_Backup
}, /* UnloopInd */
502 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
506 {ism_ignore
, ISM_DependUpon
}, /* NoEvent */
507 {ism_ignore
, ISM_DR
}, /* InterfaceUp */
508 {ism_ignore
, ISM_DR
}, /* WaitTimer */
509 {ism_ignore
, ISM_DR
}, /* BackupSeen */
510 {ism_neighbor_change
, ISM_DependUpon
}, /* NeighborChange */
511 {ism_loop_ind
, ISM_Loopback
}, /* LoopInd */
512 {ism_ignore
, ISM_DR
}, /* UnloopInd */
513 {ism_interface_down
, ISM_Down
}, /* InterfaceDown */
517 static const char *ospf_ism_event_str
[] = {
518 "NoEvent", "InterfaceUp", "WaitTimer", "BackupSeen",
519 "NeighborChange", "LoopInd", "UnLoopInd", "InterfaceDown",
522 static void ism_change_state(struct ospf_interface
*oi
, int state
)
525 struct ospf_lsa
*lsa
;
527 /* Logging change of state. */
528 if (IS_DEBUG_OSPF(ism
, ISM_STATUS
))
529 zlog_debug("ISM[%s]: State change %s -> %s", IF_NAME(oi
),
530 lookup_msg(ospf_ism_state_msg
, oi
->state
, NULL
),
531 lookup_msg(ospf_ism_state_msg
, state
, NULL
));
533 old_state
= oi
->state
;
537 hook_call(ospf_ism_change
, oi
, state
, old_state
);
539 /* Set multicast memberships appropriately for new state. */
540 ospf_if_set_multicast(oi
);
542 if (old_state
== ISM_Down
|| state
== ISM_Down
)
543 ospf_check_abr_status(oi
->ospf
);
545 /* Originate router-LSA. */
546 if (state
== ISM_Down
) {
547 if (oi
->area
->act_ints
> 0)
548 oi
->area
->act_ints
--;
549 } else if (old_state
== ISM_Down
)
550 oi
->area
->act_ints
++;
552 /* schedule router-LSA originate. */
553 ospf_router_lsa_update_area(oi
->area
);
555 /* Originate network-LSA. */
556 if (old_state
!= ISM_DR
&& state
== ISM_DR
)
557 ospf_network_lsa_update(oi
);
558 else if (old_state
== ISM_DR
&& state
!= ISM_DR
) {
559 /* Free self originated network LSA. */
560 lsa
= oi
->network_lsa_self
;
562 ospf_lsa_flush_area(lsa
, oi
->area
);
564 ospf_lsa_unlock(&oi
->network_lsa_self
);
565 oi
->network_lsa_self
= NULL
;
568 ospf_opaque_ism_change(oi
, old_state
);
570 /* Check area border status. */
571 ospf_check_abr_status(oi
->ospf
);
574 /* Execute ISM event process. */
575 int ospf_ism_event(struct thread
*thread
)
579 struct ospf_interface
*oi
;
581 oi
= THREAD_ARG(thread
);
582 event
= THREAD_VAL(thread
);
585 next_state
= (*(ISM
[oi
->state
][event
].func
))(oi
);
588 next_state
= ISM
[oi
->state
][event
].next_state
;
590 if (IS_DEBUG_OSPF(ism
, ISM_EVENTS
))
591 zlog_debug("ISM[%s]: %s (%s)", IF_NAME(oi
),
592 lookup_msg(ospf_ism_state_msg
, oi
->state
, NULL
),
593 ospf_ism_event_str
[event
]);
595 /* If state is changed. */
596 if (next_state
!= oi
->state
)
597 ism_change_state(oi
, next_state
);
599 /* Make sure timer is set. */