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 48/* elect DR and BDR. Refer to RFC2319 section 9.4 */ 49static struct ospf_neighbor * 50ospf_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 74static struct ospf_neighbor * 75ospf_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 112static struct ospf_neighbor * 113ospf_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 154static int 155ospf_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 165static void 166ospf_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. */ 183static void 184ospf_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 200static int 201ospf_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 207 /* backup current values. */ 208 old_dr = DR (oi); 209 old_bdr = BDR (oi); 210 old_state = oi->state; 211 212 el_list = list_new (); 213 214 /* List eligible routers. */ 215 ospf_dr_eligible_routers (oi->nbrs, el_list); 216 217 /* First election of DR and BDR. */ 218 ospf_elect_bdr (oi, el_list); 219 ospf_elect_dr (oi, el_list); 220 221 new_state = ospf_ism_state (oi); 222 223 zlog_debug ("DR-Election[1st]: Backup %s", inet_ntoa (BDR (oi))); 224 zlog_debug ("DR-Election[1st]: DR %s", inet_ntoa (DR (oi))); 225 226 if (new_state != old_state && 227 !(new_state == ISM_DROther && old_state < ISM_DROther)) 228 { 229 ospf_elect_bdr (oi, el_list); 230 ospf_elect_dr (oi, el_list); 231 232 new_state = ospf_ism_state (oi); 233 234 zlog_debug ("DR-Election[2nd]: Backup %s", inet_ntoa (BDR (oi))); 235 zlog_debug ("DR-Election[2nd]: DR %s", inet_ntoa (DR (oi))); 236 } 237 238 list_delete (el_list); 239 240 /* if DR or BDR changes, cause AdjOK? neighbor event. */ 241 if (!IPV4_ADDR_SAME (&old_dr, &DR (oi)) || 242 !IPV4_ADDR_SAME (&old_bdr, &BDR (oi))) 243 ospf_dr_change (oi->ospf, oi->nbrs); 244 245 return new_state; 246} 247 248 249int 250ospf_hello_timer (struct thread *thread) 251{ 252 struct ospf_interface *oi; 253 254 oi = THREAD_ARG (thread); 255 oi->t_hello = NULL; 256 257 if (IS_DEBUG_OSPF (ism, ISM_TIMERS)) 258 zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Hello timer expire)", 259 IF_NAME (oi)); 260 261 /* Sending hello packet. */ 262 ospf_hello_send (oi); 263 264 /* Hello timer set. */ 265 OSPF_HELLO_TIMER_ON (oi); 266 267 return 0; 268} 269 270static int 271ospf_wait_timer (struct thread *thread) 272{ 273 struct ospf_interface *oi; 274 275 oi = THREAD_ARG (thread); 276 oi->t_wait = NULL; 277 278 if (IS_DEBUG_OSPF (ism, ISM_TIMERS)) 279 zlog (NULL, LOG_DEBUG, "ISM[%s]: Timer (Wait timer expire)", 280 IF_NAME (oi)); 281 282 OSPF_ISM_EVENT_SCHEDULE (oi, ISM_WaitTimer); 283 284 return 0; 285} 286 287/* Hook function called after ospf ISM event is occured. And vty's 288 network command invoke this function after making interface 289 structure. */ 290static void 291ism_timer_set (struct ospf_interface *oi) 292{ 293 switch (oi->state) 294 { 295 case ISM_Down: 296 /* First entry point of ospf interface state machine. In this state 297 interface parameters must be set to initial values, and timers are 298 reset also. */ 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); 302 break; 303 case ISM_Loopback: 304 /* In this state, the interface may be looped back and will be 305 unavailable for regular data traffic. */ 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_Waiting: 311 /* The router is trying to determine the identity of DRouter and 312 BDRouter. The router begin to receive and send Hello Packets. */ 313 /* send first hello immediately */ 314 OSPF_ISM_TIMER_MSEC_ON (oi->t_hello, ospf_hello_timer, 1); 315 OSPF_ISM_TIMER_ON (oi->t_wait, ospf_wait_timer, 316 OSPF_IF_PARAM (oi, v_wait)); 317 OSPF_ISM_TIMER_OFF (oi->t_ls_ack); 318 break; 319 case ISM_PointToPoint: 320 /* The interface connects to a physical Point-to-point network or 321 virtual link. The router attempts to form an adjacency with 322 neighboring router. Hello packets are also sent. */ 323 /* send first hello immediately */ 324 OSPF_ISM_TIMER_MSEC_ON (oi->t_hello, ospf_hello_timer, 1); 325 OSPF_ISM_TIMER_OFF (oi->t_wait); 326 OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack); 327 break; 328 case ISM_DROther: 329 /* The network type of the interface is broadcast or NBMA network, 330 and the router itself is neither Designated Router nor 331 Backup Designated Router. */ 332 OSPF_HELLO_TIMER_ON (oi); 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_Backup: 337 /* The network type of the interface is broadcast os NBMA network, 338 and the router is Backup Designated Router. */ 339 OSPF_HELLO_TIMER_ON (oi); 340 OSPF_ISM_TIMER_OFF (oi->t_wait); 341 OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack); 342 break; 343 case ISM_DR: 344 /* The network type of the interface is broadcast or NBMA network, 345 and the router is Designated Router. */ 346 OSPF_HELLO_TIMER_ON (oi); 347 OSPF_ISM_TIMER_OFF (oi->t_wait); 348 OSPF_ISM_TIMER_ON (oi->t_ls_ack, ospf_ls_ack_timer, oi->v_ls_ack); 349 break; 350 } 351} 352 353static int 354ism_interface_up (struct ospf_interface *oi) 355{ 356 int next_state = 0; 357 358 /* if network type is point-to-point, Point-to-MultiPoint or virtual link, 359 the state transitions to Point-to-Point. */ 360 if (oi->type == OSPF_IFTYPE_POINTOPOINT || 361 oi->type == OSPF_IFTYPE_POINTOMULTIPOINT || 362 oi->type == OSPF_IFTYPE_VIRTUALLINK) 363 next_state = ISM_PointToPoint; 364 /* Else if the router is not eligible to DR, the state transitions to 365 DROther. */ 366 else if (PRIORITY (oi) == 0) /* router is eligible? */ 367 next_state = ISM_DROther; 368 else 369 /* Otherwise, the state transitions to Waiting. */ 370 next_state = ISM_Waiting; 371 372 if (oi->type == OSPF_IFTYPE_NBMA) 373 ospf_nbr_nbma_if_update (oi->ospf, oi); 374 375 /* ospf_ism_event (t); */ 376 return next_state; 377} 378 379static int 380ism_loop_ind (struct ospf_interface *oi) 381{ 382 int ret = 0; 383 384 /* call ism_interface_down. */ 385 /* ret = ism_interface_down (oi); */ 386 387 return ret; 388} 389 390/* Interface down event handler. */ 391static int 392ism_interface_down (struct ospf_interface *oi) 393{ 394 ospf_if_cleanup (oi); 395 return 0; 396} 397 398 399static int 400ism_backup_seen (struct ospf_interface *oi) 401{ 402 return ospf_dr_election (oi); 403} 404 405static int 406ism_wait_timer (struct ospf_interface *oi) 407{ 408 return ospf_dr_election (oi); 409} 410 411static int 412ism_neighbor_change (struct ospf_interface *oi) 413{ 414 return ospf_dr_election (oi); 415} 416 417static int 418ism_ignore (struct ospf_interface *oi) 419{ 420 if (IS_DEBUG_OSPF (ism, ISM_EVENTS)) 421 zlog (NULL, LOG_DEBUG, "ISM[%s]: ism_ignore called", IF_NAME (oi)); 422 423 return 0; 424} 425 426/* Interface State Machine */ 427struct { 428 int (*func) (struct ospf_interface *); 429 int next_state; 430} ISM [OSPF_ISM_STATE_MAX][OSPF_ISM_EVENT_MAX] = 431{ 432 { 433 /* DependUpon: dummy state. */ 434 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 435 { ism_ignore, ISM_DependUpon }, /* InterfaceUp */ 436 { ism_ignore, ISM_DependUpon }, /* WaitTimer */ 437 { ism_ignore, ISM_DependUpon }, /* BackupSeen */ 438 { ism_ignore, ISM_DependUpon }, /* NeighborChange */ 439 { ism_ignore, ISM_DependUpon }, /* LoopInd */ 440 { ism_ignore, ISM_DependUpon }, /* UnloopInd */ 441 { ism_ignore, ISM_DependUpon }, /* InterfaceDown */ 442 }, 443 { 444 /* Down:*/ 445 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 446 { ism_interface_up, ISM_DependUpon }, /* InterfaceUp */ 447 { ism_ignore, ISM_Down }, /* WaitTimer */ 448 { ism_ignore, ISM_Down }, /* BackupSeen */ 449 { ism_ignore, ISM_Down }, /* NeighborChange */ 450 { ism_loop_ind, ISM_Loopback }, /* LoopInd */ 451 { ism_ignore, ISM_Down }, /* UnloopInd */ 452 { ism_interface_down, ISM_Down }, /* InterfaceDown */ 453 }, 454 { 455 /* Loopback: */ 456 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 457 { ism_ignore, ISM_Loopback }, /* InterfaceUp */ 458 { ism_ignore, ISM_Loopback }, /* WaitTimer */ 459 { ism_ignore, ISM_Loopback }, /* BackupSeen */ 460 { ism_ignore, ISM_Loopback }, /* NeighborChange */ 461 { ism_ignore, ISM_Loopback }, /* LoopInd */ 462 { ism_ignore, ISM_Down }, /* UnloopInd */ 463 { ism_interface_down, ISM_Down }, /* InterfaceDown */ 464 }, 465 { 466 /* Waiting: */ 467 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 468 { ism_ignore, ISM_Waiting }, /* InterfaceUp */ 469 { ism_wait_timer, ISM_DependUpon }, /* WaitTimer */ 470 { ism_backup_seen, ISM_DependUpon }, /* BackupSeen */ 471 { ism_ignore, ISM_Waiting }, /* NeighborChange */ 472 { ism_loop_ind, ISM_Loopback }, /* LoopInd */ 473 { ism_ignore, ISM_Waiting }, /* UnloopInd */ 474 { ism_interface_down, ISM_Down }, /* InterfaceDown */ 475 }, 476 { 477 /* Point-to-Point: */ 478 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 479 { ism_ignore, ISM_PointToPoint }, /* InterfaceUp */ 480 { ism_ignore, ISM_PointToPoint }, /* WaitTimer */ 481 { ism_ignore, ISM_PointToPoint }, /* BackupSeen */ 482 { ism_ignore, ISM_PointToPoint }, /* NeighborChange */ 483 { ism_loop_ind, ISM_Loopback }, /* LoopInd */ 484 { ism_ignore, ISM_PointToPoint }, /* UnloopInd */ 485 { ism_interface_down, ISM_Down }, /* InterfaceDown */ 486 }, 487 { 488 /* DROther: */ 489 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 490 { ism_ignore, ISM_DROther }, /* InterfaceUp */ 491 { ism_ignore, ISM_DROther }, /* WaitTimer */ 492 { ism_ignore, ISM_DROther }, /* BackupSeen */ 493 { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */ 494 { ism_loop_ind, ISM_Loopback }, /* LoopInd */ 495 { ism_ignore, ISM_DROther }, /* UnloopInd */ 496 { ism_interface_down, ISM_Down }, /* InterfaceDown */ 497 }, 498 { 499 /* Backup: */ 500 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 501 { ism_ignore, ISM_Backup }, /* InterfaceUp */ 502 { ism_ignore, ISM_Backup }, /* WaitTimer */ 503 { ism_ignore, ISM_Backup }, /* BackupSeen */ 504 { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */ 505 { ism_loop_ind, ISM_Loopback }, /* LoopInd */ 506 { ism_ignore, ISM_Backup }, /* UnloopInd */ 507 { ism_interface_down, ISM_Down }, /* InterfaceDown */ 508 }, 509 { 510 /* DR: */ 511 { ism_ignore, ISM_DependUpon }, /* NoEvent */ 512 { ism_ignore, ISM_DR }, /* InterfaceUp */ 513 { ism_ignore, ISM_DR }, /* WaitTimer */ 514 { ism_ignore, ISM_DR }, /* BackupSeen */ 515 { ism_neighbor_change, ISM_DependUpon }, /* NeighborChange */ 516 { ism_loop_ind, ISM_Loopback }, /* LoopInd */ 517 { ism_ignore, ISM_DR }, /* UnloopInd */ 518 { ism_interface_down, ISM_Down }, /* InterfaceDown */ 519 }, 520}; 521 522static const char *ospf_ism_event_str[] = 523{ 524 "NoEvent", 525 "InterfaceUp", 526 "WaitTimer", 527 "BackupSeen", 528 "NeighborChange", 529 "LoopInd", 530 "UnLoopInd", 531 "InterfaceDown", 532}; 533 534static void 535ism_change_state (struct ospf_interface *oi, int state) 536{ 537 int old_state; 538 struct ospf_lsa *lsa; 539 540 /* Logging change of state. */ 541 if (IS_DEBUG_OSPF (ism, ISM_STATUS)) 542 zlog (NULL, LOG_DEBUG, "ISM[%s]: State change %s -> %s", IF_NAME (oi), 543 LOOKUP (ospf_ism_state_msg, oi->state), 544 LOOKUP (ospf_ism_state_msg, state)); 545 546 old_state = oi->state; 547 oi->state = state; 548 oi->state_change++; 549 550#ifdef HAVE_SNMP 551 /* Terminal state or regression */ 552 if ((state == ISM_DR) || (state == ISM_Backup) || (state == ISM_DROther) || 553 (state == ISM_PointToPoint) || (state < old_state)) 554 { 555 /* ospfVirtIfStateChange */ 556 if (oi->type == OSPF_IFTYPE_VIRTUALLINK) 557 ospfTrapVirtIfStateChange (oi); 558 /* ospfIfStateChange */ 559 else 560 ospfTrapIfStateChange (oi); 561 } 562#endif 563 564 /* Set multicast memberships appropriately for new state. */ 565 ospf_if_set_multicast(oi); 566 567 if (old_state == ISM_Down || state == ISM_Down) 568 ospf_check_abr_status (oi->ospf); 569 570 /* Originate router-LSA. */ 571 if (state == ISM_Down) 572 { 573 if (oi->area->act_ints > 0) 574 oi->area->act_ints--; 575 } 576 else if (old_state == ISM_Down) 577 oi->area->act_ints++; 578 579 /* schedule router-LSA originate. */ 580 ospf_router_lsa_update_area (oi->area); 581 582 /* Originate network-LSA. */ 583 if (old_state != ISM_DR && state == ISM_DR) 584 ospf_network_lsa_update (oi); 585 else if (old_state == ISM_DR && state != ISM_DR) 586 { 587 /* Free self originated network LSA. */ 588 lsa = oi->network_lsa_self; 589 if (lsa) 590 ospf_lsa_flush_area (lsa, oi->area); 591 592 ospf_lsa_unlock (&oi->network_lsa_self); 593 oi->network_lsa_self = NULL; 594 } 595 596#ifdef HAVE_OPAQUE_LSA 597 ospf_opaque_ism_change (oi, old_state); 598#endif /* HAVE_OPAQUE_LSA */ 599 600 /* Check area border status. */ 601 ospf_check_abr_status (oi->ospf); 602} 603 604/* Execute ISM event process. */ 605int 606ospf_ism_event (struct thread *thread) 607{ 608 int event; 609 int next_state; 610 struct ospf_interface *oi; 611 612 oi = THREAD_ARG (thread); 613 event = THREAD_VAL (thread); 614 615 /* Call function. */ 616 next_state = (*(ISM [oi->state][event].func))(oi); 617 618 if (! next_state) 619 next_state = ISM [oi->state][event].next_state; 620 621 if (IS_DEBUG_OSPF (ism, ISM_EVENTS)) 622 zlog (NULL, LOG_DEBUG, "ISM[%s]: %s (%s)", IF_NAME (oi), 623 LOOKUP (ospf_ism_state_msg, oi->state), 624 ospf_ism_event_str[event]); 625 626 /* If state is changed. */ 627 if (next_state != oi->state) 628 ism_change_state (oi, next_state); 629 630 /* Make sure timer is set. */ 631 ism_timer_set (oi); 632 633 return 0; 634} 635 636