]> git.proxmox.com Git - mirror_frr.git/blob - ospfd/ospf_ism.c
2005-04-07 Paul Jakma <paul.jakma@sun.com>
[mirror_frr.git] / ospfd / ospf_ism.c
1 /*
2 * OSPF version 2 Interface State Machine
3 * From RFC2328 [OSPF Version 2]
4 * Copyright (C) 1999, 2000 Toshiaki Takada
5 *
6 * This file is part of GNU Zebra.
7 *
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
11 * later version.
12 *
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.
17 *
18 * You should have received a copy of the GNU General Public License
19 * along with GNU Zebra; see the file COPYING. If not, write to the Free
20 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
21 * 02111-1307, USA.
22 */
23
24 #include <zebra.h>
25
26 #include "thread.h"
27 #include "linklist.h"
28 #include "prefix.h"
29 #include "if.h"
30 #include "table.h"
31 #include "log.h"
32
33 #include "ospfd/ospfd.h"
34 #include "ospfd/ospf_interface.h"
35 #include "ospfd/ospf_ism.h"
36 #include "ospfd/ospf_asbr.h"
37 #include "ospfd/ospf_lsa.h"
38 #include "ospfd/ospf_lsdb.h"
39 #include "ospfd/ospf_neighbor.h"
40 #include "ospfd/ospf_nsm.h"
41 #include "ospfd/ospf_network.h"
42 #include "ospfd/ospf_dump.h"
43 #include "ospfd/ospf_packet.h"
44 #include "ospfd/ospf_flood.h"
45 #include "ospfd/ospf_abr.h"
46 \f
47 /* elect DR and BDR. Refer to RFC2319 section 9.4 */
48 struct ospf_neighbor *
49 ospf_dr_election_sub (struct list *routers)
50 {
51 struct listnode *node;
52 struct ospf_neighbor *nbr, *max = NULL;
53
54 /* Choose highest router priority.
55 In case of tie, choose highest Router ID. */
56 for (ALL_LIST_ELEMENTS_RO (routers, node, nbr))
57 {
58 if (max == NULL)
59 max = nbr;
60 else
61 {
62 if (max->priority < nbr->priority)
63 max = nbr;
64 else if (max->priority == nbr->priority)
65 if (IPV4_ADDR_CMP (&max->router_id, &nbr->router_id) < 0)
66 max = nbr;
67 }
68 }
69
70 return max;
71 }
72
73 struct ospf_neighbor *
74 ospf_elect_dr (struct ospf_interface *oi, struct list *el_list)
75 {
76 struct list *dr_list;
77 struct listnode *node;
78 struct ospf_neighbor *nbr, *dr = NULL, *bdr = NULL;
79
80 dr_list = list_new ();
81
82 /* Add neighbors to the list. */
83 for (ALL_LIST_ELEMENTS_RO (el_list, node, nbr))
84 {
85 /* neighbor declared to be DR. */
86 if (NBR_IS_DR (nbr))
87 listnode_add (dr_list, nbr);
88
89 /* Preserve neighbor BDR. */
90 if (IPV4_ADDR_SAME (&BDR (oi), &nbr->address.u.prefix4))
91 bdr = nbr;
92 }
93
94 /* Elect Designated Router. */
95 if (listcount (dr_list) > 0)
96 dr = ospf_dr_election_sub (dr_list);
97 else
98 dr = bdr;
99
100 /* Set DR to interface. */
101 if (dr)
102 {
103 DR (oi) = dr->address.u.prefix4;
104 dr->d_router = dr->address.u.prefix4;
105 }
106 else
107 DR (oi).s_addr = 0;
108
109 list_delete (dr_list);
110
111 return dr;
112 }
113
114 struct ospf_neighbor *
115 ospf_elect_bdr (struct ospf_interface *oi, struct list *el_list)
116 {
117 struct list *bdr_list, *no_dr_list;
118 struct listnode *node;
119 struct ospf_neighbor *nbr, *bdr = NULL;
120
121 bdr_list = list_new ();
122 no_dr_list = list_new ();
123
124 /* Add neighbors to the list. */
125 for (ALL_LIST_ELEMENTS_RO (el_list, node, nbr))
126 {
127 /* neighbor declared to be DR. */
128 if (NBR_IS_DR (nbr))
129 continue;
130
131 /* neighbor declared to be BDR. */
132 if (NBR_IS_BDR (nbr))
133 listnode_add (bdr_list, nbr);
134
135 listnode_add (no_dr_list, nbr);
136 }
137
138 /* Elect Backup Designated Router. */
139 if (listcount (bdr_list) > 0)
140 bdr = ospf_dr_election_sub (bdr_list);
141 else
142 bdr = ospf_dr_election_sub (no_dr_list);
143
144 /* Set BDR to interface. */
145 if (bdr)
146 {
147 BDR (oi) = bdr->address.u.prefix4;
148 bdr->bd_router = bdr->address.u.prefix4;
149 }
150 else
151 BDR (oi).s_addr = 0;
152
153 list_delete (bdr_list);
154 list_delete (no_dr_list);
155
156 return bdr;
157 }
158
159 int
160 ospf_ism_state (struct ospf_interface *oi)
161 {
162 if (IPV4_ADDR_SAME (&DR (oi), &oi->address->u.prefix4))
163 return ISM_DR;
164 else if (IPV4_ADDR_SAME (&BDR (oi), &oi->address->u.prefix4))
165 return ISM_Backup;
166 else
167 return ISM_DROther;
168 }
169
170 void
171 ospf_dr_eligible_routers (struct route_table *nbrs, struct list *el_list)
172 {
173 struct route_node *rn;
174 struct ospf_neighbor *nbr;
175
176 for (rn = route_top (nbrs); rn; rn = route_next (rn))
177 if ((nbr = rn->info) != NULL)
178 /* Ignore 0.0.0.0 node*/
179 if (nbr->router_id.s_addr != 0)
180 /* Is neighbor eligible? */
181 if (nbr->priority != 0)
182 /* Is neighbor upper 2-Way? */
183 if (nbr->state >= NSM_TwoWay)
184 listnode_add (el_list, nbr);
185 }
186
187 /* Generate AdjOK? NSM event. */
188 void
189 ospf_dr_change (struct ospf *ospf, struct route_table *nbrs)
190 {
191 struct route_node *rn;
192 struct ospf_neighbor *nbr;
193
194 for (rn = route_top (nbrs); rn; rn = route_next (rn))
195 if ((nbr = rn->info) != NULL)
196 /* Ignore 0.0.0.0 node*/
197 if (nbr->router_id.s_addr != 0)
198 /* Is neighbor upper 2-Way? */
199 if (nbr->state >= NSM_TwoWay)
200 /* Ignore myself. */
201 if (!IPV4_ADDR_SAME (&nbr->router_id, &ospf->router_id))
202 OSPF_NSM_EVENT_SCHEDULE (nbr, NSM_AdjOK);
203 }
204
205 int
206 ospf_dr_election (struct ospf_interface *oi)
207 {
208 struct in_addr old_dr, old_bdr;
209 int old_state, new_state;
210 struct list *el_list;
211 struct ospf_neighbor *dr, *bdr;
212
213 /* backup current values. */
214 old_dr = DR (oi);
215 old_bdr = BDR (oi);
216 old_state = oi->state;
217
218 el_list = list_new ();
219
220 /* List eligible routers. */
221 ospf_dr_eligible_routers (oi->nbrs, el_list);
222
223 /* First election of DR and BDR. */
224 bdr = ospf_elect_bdr (oi, el_list);
225 dr = ospf_elect_dr (oi, el_list);
226
227 new_state = ospf_ism_state (oi);
228
229 zlog_info ("DR-Election[1st]: Backup %s", inet_ntoa (BDR (oi)));
230 zlog_info ("DR-Election[1st]: DR %s", inet_ntoa (DR (oi)));
231
232 if (new_state != old_state &&
233 !(new_state == ISM_DROther && old_state < ISM_DROther))
234 {
235 ospf_elect_bdr (oi, el_list);
236 ospf_elect_dr (oi, el_list);
237
238 new_state = ospf_ism_state (oi);
239
240 zlog_info ("DR-Election[2nd]: Backup %s", inet_ntoa (BDR (oi)));
241 zlog_info ("DR-Election[2nd]: DR %s", inet_ntoa (DR (oi)));
242 }
243
244 list_delete (el_list);
245
246 /* if DR or BDR changes, cause AdjOK? neighbor event. */
247 if (!IPV4_ADDR_SAME (&old_dr, &DR (oi)) ||
248 !IPV4_ADDR_SAME (&old_bdr, &BDR (oi)))
249 ospf_dr_change (oi->ospf, oi->nbrs);
250
251 return new_state;
252 }
253
254 \f
255 int
256 ospf_hello_timer (struct thread *thread)
257 {
258 struct ospf_interface *oi;
259
260 oi = THREAD_ARG (thread);
261 oi->t_hello = NULL;
262
263 if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
264 zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Hello timer expire)",
265 IF_NAME (oi));
266
267 /* Sending hello packet. */
268 ospf_hello_send (oi);
269
270 /* Hello timer set. */
271 OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
272 OSPF_IF_PARAM (oi, v_hello));
273
274 return 0;
275 }
276
277 int
278 ospf_wait_timer (struct thread *thread)
279 {
280 struct ospf_interface *oi;
281
282 oi = THREAD_ARG (thread);
283 oi->t_wait = NULL;
284
285 if (IS_DEBUG_OSPF (ism, ISM_TIMERS))
286 zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Wait timer expire)",
287 IF_NAME (oi));
288
289 OSPF_ISM_EVENT_SCHEDULE (oi, ISM_WaitTimer);
290
291 return 0;
292 }
293
294 /* Hook function called after ospf ISM event is occured. And vty's
295 network command invoke this function after making interface
296 structure. */
297 void
298 ism_timer_set (struct ospf_interface *oi)
299 {
300 switch (oi->state)
301 {
302 case ISM_Down:
303 /* First entry point of ospf interface state machine. In this state
304 interface parameters must be set to initial values, and timers are
305 reset also. */
306 OSPF_ISM_TIMER_OFF (oi->t_hello);
307 OSPF_ISM_TIMER_OFF (oi->t_wait);
308 OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
309 break;
310 case ISM_Loopback:
311 /* In this state, the interface may be looped back and will be
312 unavailable for regular data traffic. */
313 OSPF_ISM_TIMER_OFF (oi->t_hello);
314 OSPF_ISM_TIMER_OFF (oi->t_wait);
315 OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
316 break;
317 case ISM_Waiting:
318 /* The router is trying to determine the identity of DRouter and
319 BDRouter. The router begin to receive and send Hello Packets. */
320 /* send first hello immediately */
321 OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer, 1);
322 OSPF_ISM_TIMER_ON (oi->t_wait, ospf_wait_timer,
323 OSPF_IF_PARAM (oi, v_wait));
324 OSPF_ISM_TIMER_OFF (oi->t_ls_ack);
325 break;
326 case ISM_PointToPoint:
327 /* The interface connects to a physical Point-to-point network or
328 virtual link. The router attempts to form an adjacency with
329 neighboring router. Hello packets are also sent. */
330 /* send first hello immediately */
331 OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer, 1);
332
333 OSPF_ISM_TIMER_OFF (oi->t_wait);
334 OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
335 break;
336 case ISM_DROther:
337 /* The network type of the interface is broadcast or NBMA network,
338 and the router itself is neither Designated Router nor
339 Backup Designated Router. */
340 OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
341 OSPF_IF_PARAM (oi, v_hello));
342 OSPF_ISM_TIMER_OFF (oi->t_wait);
343 OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
344 break;
345 case ISM_Backup:
346 /* The network type of the interface is broadcast os NBMA network,
347 and the router is Backup Designated Router. */
348 OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
349 OSPF_IF_PARAM (oi, v_hello));
350 OSPF_ISM_TIMER_OFF (oi->t_wait);
351 OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
352 break;
353 case ISM_DR:
354 /* The network type of the interface is broadcast or NBMA network,
355 and the router is Designated Router. */
356 OSPF_ISM_TIMER_ON (oi->t_hello, ospf_hello_timer,
357 OSPF_IF_PARAM (oi, v_hello));
358 OSPF_ISM_TIMER_OFF (oi->t_wait);
359 OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack);
360 break;
361 }
362 }
363
364 int
365 ism_stop (struct ospf_interface *oi)
366 {
367 return 0;
368 }
369
370 int
371 ism_interface_up (struct ospf_interface *oi)
372 {
373 int next_state = 0;
374
375 /* if network type is point-to-point, Point-to-MultiPoint or virtual link,
376 the state transitions to Point-to-Point. */
377 if (oi->type == OSPF_IFTYPE_POINTOPOINT ||
378 oi->type == OSPF_IFTYPE_POINTOMULTIPOINT ||
379 oi->type == OSPF_IFTYPE_VIRTUALLINK)
380 next_state = ISM_PointToPoint;
381 /* Else if the router is not eligible to DR, the state transitions to
382 DROther. */
383 else if (PRIORITY (oi) == 0) /* router is eligible? */
384 next_state = ISM_DROther;
385 else
386 /* Otherwise, the state transitions to Waiting. */
387 next_state = ISM_Waiting;
388
389 if (oi->type == OSPF_IFTYPE_NBMA)
390 ospf_nbr_nbma_if_update (oi->ospf, oi);
391
392 /* ospf_ism_event (t); */
393 return next_state;
394 }
395
396 int
397 ism_loop_ind (struct ospf_interface *oi)
398 {
399 int ret = 0;
400
401 /* call ism_interface_down. */
402 /* ret = ism_interface_down (oi); */
403
404 return ret;
405 }
406
407 /* Interface down event handler. */
408 int
409 ism_interface_down (struct ospf_interface *oi)
410 {
411 ospf_if_cleanup (oi);
412 return 0;
413 }
414
415
416 int
417 ism_backup_seen (struct ospf_interface *oi)
418 {
419 return ospf_dr_election (oi);
420 }
421
422 int
423 ism_wait_timer (struct ospf_interface *oi)
424 {
425 return ospf_dr_election (oi);
426 }
427
428 int
429 ism_neighbor_change (struct ospf_interface *oi)
430 {
431 return ospf_dr_election (oi);
432 }
433
434 int
435 ism_ignore (struct ospf_interface *oi)
436 {
437 if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
438 zlog (NULL, LOG_DEBUG, "ISM[%s]: ism_ignore called", IF_NAME (oi));
439
440 return 0;
441 }
442
443 /* Interface State Machine */
444 struct {
445 int (*func) ();
446 int next_state;
447 } ISM [OSPF_ISM_STATE_MAX][OSPF_ISM_EVENT_MAX] =
448 {
449 {
450 /* DependUpon: dummy state. */
451 { ism_ignore, ISM_DependUpon }, /* NoEvent */
452 { ism_ignore, ISM_DependUpon }, /* InterfaceUp */
453 { ism_ignore, ISM_DependUpon }, /* WaitTimer */
454 { ism_ignore, ISM_DependUpon }, /* BackupSeen */
455 { ism_ignore, ISM_DependUpon }, /* NeighborChange */
456 { ism_ignore, ISM_DependUpon }, /* LoopInd */
457 { ism_ignore, ISM_DependUpon }, /* UnloopInd */
458 { ism_ignore, ISM_DependUpon }, /* InterfaceDown */
459 },
460 {
461 /* Down:*/
462 { ism_ignore, ISM_DependUpon }, /* NoEvent */
463 { ism_interface_up, ISM_DependUpon }, /* InterfaceUp */
464 { ism_ignore, ISM_Down }, /* WaitTimer */
465 { ism_ignore, ISM_Down }, /* BackupSeen */
466 { ism_ignore, ISM_Down }, /* NeighborChange */
467 { ism_loop_ind, ISM_Loopback }, /* LoopInd */
468 { ism_ignore, ISM_Down }, /* UnloopInd */
469 { ism_interface_down, ISM_Down }, /* InterfaceDown */
470 },
471 {
472 /* Loopback: */
473 { ism_ignore, ISM_DependUpon }, /* NoEvent */
474 { ism_ignore, ISM_Loopback }, /* InterfaceUp */
475 { ism_ignore, ISM_Loopback }, /* WaitTimer */
476 { ism_ignore, ISM_Loopback }, /* BackupSeen */
477 { ism_ignore, ISM_Loopback }, /* NeighborChange */
478 { ism_ignore, ISM_Loopback }, /* LoopInd */
479 { ism_ignore, ISM_Down }, /* UnloopInd */
480 { ism_interface_down, ISM_Down }, /* InterfaceDown */
481 },
482 {
483 /* Waiting: */
484 { ism_ignore, ISM_DependUpon }, /* NoEvent */
485 { ism_ignore, ISM_Waiting }, /* InterfaceUp */
486 { ism_wait_timer, ISM_DependUpon }, /* WaitTimer */
487 { ism_backup_seen, ISM_DependUpon }, /* BackupSeen */
488 { ism_ignore, ISM_Waiting }, /* NeighborChange */
489 { ism_loop_ind, ISM_Loopback }, /* LoopInd */
490 { ism_ignore, ISM_Waiting }, /* UnloopInd */
491 { ism_interface_down, ISM_Down }, /* InterfaceDown */
492 },
493 {
494 /* Point-to-Point: */
495 { ism_ignore, ISM_DependUpon }, /* NoEvent */
496 { ism_ignore, ISM_PointToPoint }, /* InterfaceUp */
497 { ism_ignore, ISM_PointToPoint }, /* WaitTimer */
498 { ism_ignore, ISM_PointToPoint }, /* BackupSeen */
499 { ism_ignore, ISM_PointToPoint }, /* NeighborChange */
500 { ism_loop_ind, ISM_Loopback }, /* LoopInd */
501 { ism_ignore, ISM_PointToPoint }, /* UnloopInd */
502 { ism_interface_down, ISM_Down }, /* InterfaceDown */
503 },
504 {
505 /* DROther: */
506 { ism_ignore, ISM_DependUpon }, /* NoEvent */
507 { ism_ignore, ISM_DROther }, /* InterfaceUp */
508 { ism_ignore, ISM_DROther }, /* WaitTimer */
509 { ism_ignore, ISM_DROther }, /* BackupSeen */
510 { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */
511 { ism_loop_ind, ISM_Loopback }, /* LoopInd */
512 { ism_ignore, ISM_DROther }, /* UnloopInd */
513 { ism_interface_down, ISM_Down }, /* InterfaceDown */
514 },
515 {
516 /* Backup: */
517 { ism_ignore, ISM_DependUpon }, /* NoEvent */
518 { ism_ignore, ISM_Backup }, /* InterfaceUp */
519 { ism_ignore, ISM_Backup }, /* WaitTimer */
520 { ism_ignore, ISM_Backup }, /* BackupSeen */
521 { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */
522 { ism_loop_ind, ISM_Loopback }, /* LoopInd */
523 { ism_ignore, ISM_Backup }, /* UnloopInd */
524 { ism_interface_down, ISM_Down }, /* InterfaceDown */
525 },
526 {
527 /* DR: */
528 { ism_ignore, ISM_DependUpon }, /* NoEvent */
529 { ism_ignore, ISM_DR }, /* InterfaceUp */
530 { ism_ignore, ISM_DR }, /* WaitTimer */
531 { ism_ignore, ISM_DR }, /* BackupSeen */
532 { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */
533 { ism_loop_ind, ISM_Loopback }, /* LoopInd */
534 { ism_ignore, ISM_DR }, /* UnloopInd */
535 { ism_interface_down, ISM_Down }, /* InterfaceDown */
536 },
537 };
538
539 const static char *ospf_ism_event_str[] =
540 {
541 "NoEvent",
542 "InterfaceUp",
543 "WaitTimer",
544 "BackupSeen",
545 "NeighborChange",
546 "LoopInd",
547 "UnLoopInd",
548 "InterfaceDown",
549 };
550
551 void
552 ism_change_state (struct ospf_interface *oi, int state)
553 {
554 int old_state;
555 struct ospf_lsa *lsa;
556
557 /* Logging change of state. */
558 if (IS_DEBUG_OSPF (ism, ISM_STATUS))
559 zlog (NULL, LOG_DEBUG, "ISM[%s]: State change %s -> %s", IF_NAME (oi),
560 LOOKUP (ospf_ism_state_msg, oi->state),
561 LOOKUP (ospf_ism_state_msg, state));
562
563 old_state = oi->state;
564 oi->state = state;
565 oi->state_change++;
566
567 /* Set multicast memberships appropriately for new state. */
568 ospf_if_set_multicast(oi);
569
570 if (old_state == ISM_Down || state == ISM_Down)
571 ospf_check_abr_status (oi->ospf);
572
573 /* Originate router-LSA. */
574 if (oi->area)
575 {
576 if (state == ISM_Down)
577 {
578 if (oi->area->act_ints > 0)
579 oi->area->act_ints--;
580 }
581 else if (old_state == ISM_Down)
582 oi->area->act_ints++;
583
584 /* schedule router-LSA originate. */
585 ospf_router_lsa_timer_add (oi->area);
586 }
587
588 /* Originate network-LSA. */
589 if (old_state != ISM_DR && state == ISM_DR)
590 ospf_network_lsa_timer_add (oi);
591 else if (old_state == ISM_DR && state != ISM_DR)
592 {
593 /* Free self originated network LSA. */
594 lsa = oi->network_lsa_self;
595 if (lsa)
596 {
597 ospf_lsa_flush_area (lsa, oi->area);
598 OSPF_TIMER_OFF (oi->t_network_lsa_self);
599 }
600
601 ospf_lsa_unlock (oi->network_lsa_self);
602 oi->network_lsa_self = NULL;
603 }
604
605 #ifdef HAVE_OPAQUE_LSA
606 ospf_opaque_ism_change (oi, old_state);
607 #endif /* HAVE_OPAQUE_LSA */
608
609 /* Check area border status. */
610 ospf_check_abr_status (oi->ospf);
611 }
612
613 /* Execute ISM event process. */
614 int
615 ospf_ism_event (struct thread *thread)
616 {
617 int event;
618 int next_state;
619 struct ospf_interface *oi;
620
621 oi = THREAD_ARG (thread);
622 event = THREAD_VAL (thread);
623
624 /* Call function. */
625 next_state = (*(ISM [oi->state][event].func))(oi);
626
627 if (! next_state)
628 next_state = ISM [oi->state][event].next_state;
629
630 if (IS_DEBUG_OSPF (ism, ISM_EVENTS))
631 zlog (NULL, LOG_DEBUG, "ISM[%s]: %s (%s)", IF_NAME (oi),
632 LOOKUP (ospf_ism_state_msg, oi->state),
633 ospf_ism_event_str[event]);
634
635 /* If state is changed. */
636 if (next_state != oi->state)
637 ism_change_state (oi, next_state);
638
639 /* Make sure timer is set. */
640 ism_timer_set (oi);
641
642 return 0;
643 }
644