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