ospfd/ospf_nsm.c

   1 /*
   2  * OSPF version 2  Neighbor 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 "memory.h"
  28 #include "hash.h"
  29 #include "linklist.h"
  30 #include "prefix.h"
  31 #include "if.h"
  32 #include "table.h"
  33 #include "stream.h"
  34 #include "table.h"
  35 #include "log.h"
  36
  37 #include "ospfd/ospfd.h"
  38 #include "ospfd/ospf_interface.h"
  39 #include "ospfd/ospf_ism.h"
  40 #include "ospfd/ospf_asbr.h"
  41 #include "ospfd/ospf_lsa.h"
  42 #include "ospfd/ospf_lsdb.h"
  43 #include "ospfd/ospf_neighbor.h"
  44 #include "ospfd/ospf_nsm.h"
  45 #include "ospfd/ospf_network.h"
  46 #include "ospfd/ospf_packet.h"
  47 #include "ospfd/ospf_dump.h"
  48 #include "ospfd/ospf_flood.h"
  49 #include "ospfd/ospf_abr.h"
  50 #include "ospfd/ospf_snmp.h"
  51
  52 static void nsm_clear_adj (struct ospf_neighbor *);
  53 \f
  54 /* OSPF NSM Timer functions. */
  55 static int
  56 ospf_inactivity_timer (struct thread *thread)
  57 {
  58   struct ospf_neighbor *nbr;
  59
  60   nbr = THREAD_ARG (thread);
  61   nbr->t_inactivity = NULL;
  62
  63   if (IS_DEBUG_OSPF (nsm, NSM_TIMERS))
  64     zlog (NULL, LOG_DEBUG, "NSM[%s:%s]: Timer (Inactivity timer expire)",
  65           IF_NAME (nbr->oi), inet_ntoa (nbr->router_id));
  66
  67   OSPF_NSM_EVENT_SCHEDULE (nbr, NSM_InactivityTimer);
  68
  69   return 0;
  70 }
  71
  72 static int
  73 ospf_db_desc_timer (struct thread *thread)
  74 {
  75   struct ospf_interface *oi;
  76   struct ospf_neighbor *nbr;
  77
  78   nbr = THREAD_ARG (thread);
  79   nbr->t_db_desc = NULL;
  80
  81   oi = nbr->oi;
  82
  83   if (IS_DEBUG_OSPF (nsm, NSM_TIMERS))
  84     zlog (NULL, LOG_DEBUG, "NSM[%s:%s]: Timer (DD Retransmit timer expire)",
  85           IF_NAME (nbr->oi), inet_ntoa (nbr->src));
  86
  87   /* resent last send DD packet. */
  88   assert (nbr->last_send);
  89   ospf_db_desc_resend (nbr);
  90
  91   /* DD Retransmit timer set. */
  92   OSPF_NSM_TIMER_ON (nbr->t_db_desc, ospf_db_desc_timer, nbr->v_db_desc);
  93
  94   return 0;
  95 }
  96
  97 /* Hook function called after ospf NSM event is occured.
  98  *
  99  * Set/clear any timers whose condition is implicit to the neighbour
 100  * state. There may be other timers which are set/unset according to other
 101  * state.
 102  *
 103  * We rely on this function to properly clear timers in lower states,
 104  * particularly before deleting a neighbour.
 105  */
 106 static void
 107 nsm_timer_set (struct ospf_neighbor *nbr)
 108 {
 109   switch (nbr->state)
 110     {
 111     case NSM_Deleted:
 112     case NSM_Down:
 113       OSPF_NSM_TIMER_OFF (nbr->t_inactivity);
 114       OSPF_NSM_TIMER_OFF (nbr->t_hello_reply);
 115     case NSM_Attempt:
 116     case NSM_Init:
 117     case NSM_TwoWay:
 118       OSPF_NSM_TIMER_OFF (nbr->t_db_desc);
 119       OSPF_NSM_TIMER_OFF (nbr->t_ls_upd);
 120       OSPF_NSM_TIMER_OFF (nbr->t_ls_req);
 121       break;
 122     case NSM_ExStart:
 123       OSPF_NSM_TIMER_ON (nbr->t_db_desc, ospf_db_desc_timer, nbr->v_db_desc);
 124       OSPF_NSM_TIMER_OFF (nbr->t_ls_upd);
 125       OSPF_NSM_TIMER_OFF (nbr->t_ls_req);
 126       break;
 127     case NSM_Exchange:
 128       OSPF_NSM_TIMER_ON (nbr->t_ls_upd, ospf_ls_upd_timer, nbr->v_ls_upd);
 129       if (!IS_SET_DD_MS (nbr->dd_flags))
 130         OSPF_NSM_TIMER_OFF (nbr->t_db_desc);
 131       break;
 132     case NSM_Loading:
 133     case NSM_Full:
 134     default:
 135       OSPF_NSM_TIMER_OFF (nbr->t_db_desc);
 136       break;
 137     }
 138 }
 139
 140 /* 10.4 of RFC2328, indicate whether an adjacency is appropriate with
 141  * the given neighbour
 142  */
 143 static int
 144 nsm_should_adj (struct ospf_neighbor *nbr)
 145 {
 146   struct ospf_interface *oi = nbr->oi;
 147
 148       /* These network types must always form adjacencies. */
 149   if (oi->type == OSPF_IFTYPE_POINTOPOINT
 150       || oi->type == OSPF_IFTYPE_POINTOMULTIPOINT
 151       || oi->type == OSPF_IFTYPE_VIRTUALLINK
 152       /* Router itself is the DRouter or the BDRouter. */
 153       || IPV4_ADDR_SAME (&oi->address->u.prefix4, &DR (oi))
 154       || IPV4_ADDR_SAME (&oi->address->u.prefix4, &BDR (oi))
 155       /* Neighboring Router is the DRouter or the BDRouter. */
 156       || IPV4_ADDR_SAME (&nbr->address.u.prefix4, &DR (oi))
 157       || IPV4_ADDR_SAME (&nbr->address.u.prefix4, &BDR (oi)))
 158     return 1;
 159
 160   return 0;
 161 }
 162 \f
 163 /* OSPF NSM functions. */
 164 static int
 165 nsm_hello_received (struct ospf_neighbor *nbr)
 166 {
 167   /* Start or Restart Inactivity Timer. */
 168   OSPF_NSM_TIMER_OFF (nbr->t_inactivity);
 169
 170   OSPF_NSM_TIMER_ON (nbr->t_inactivity, ospf_inactivity_timer,
 171                      nbr->v_inactivity);
 172
 173   if (nbr->oi->type == OSPF_IFTYPE_NBMA && nbr->nbr_nbma)
 174     OSPF_POLL_TIMER_OFF (nbr->nbr_nbma->t_poll);
 175
 176   return 0;
 177 }
 178
 179 static int
 180 nsm_start (struct ospf_neighbor *nbr)
 181 {
 182   if (nbr->nbr_nbma)
 183       OSPF_POLL_TIMER_OFF (nbr->nbr_nbma->t_poll);
 184
 185   OSPF_NSM_TIMER_OFF (nbr->t_inactivity);
 186
 187   OSPF_NSM_TIMER_ON (nbr->t_inactivity, ospf_inactivity_timer,
 188                      nbr->v_inactivity);
 189
 190   return 0;
 191 }
 192
 193 static int
 194 nsm_twoway_received (struct ospf_neighbor *nbr)
 195 {
 196   return (nsm_should_adj (nbr) ? NSM_ExStart : NSM_TwoWay);
 197 }
 198
 199 int
 200 ospf_db_summary_count (struct ospf_neighbor *nbr)
 201 {
 202   return ospf_lsdb_count_all (&nbr->db_sum);
 203 }
 204
 205 int
 206 ospf_db_summary_isempty (struct ospf_neighbor *nbr)
 207 {
 208   return ospf_lsdb_isempty (&nbr->db_sum);
 209 }
 210
 211 static int
 212 ospf_db_summary_add (struct ospf_neighbor *nbr, struct ospf_lsa *lsa)
 213 {
 214 #ifdef HAVE_OPAQUE_LSA
 215   switch (lsa->data->type)
 216     {
 217     case OSPF_OPAQUE_LINK_LSA:
 218       /* Exclude type-9 LSAs that does not have the same "oi" with "nbr". */
 219       if (lsa->oi != nbr->oi)
 220           return 0;
 221       break;
 222     case OSPF_OPAQUE_AREA_LSA:
 223       /*
 224        * It is assured by the caller function "nsm_negotiation_done()"
 225        * that every given LSA belongs to the same area with "nbr".
 226        */
 227       break;
 228     case OSPF_OPAQUE_AS_LSA:
 229     default:
 230       break;
 231     }
 232 #endif /* HAVE_OPAQUE_LSA */
 233
 234   /* Stay away from any Local Translated Type-7 LSAs */
 235   if (CHECK_FLAG (lsa->flags, OSPF_LSA_LOCAL_XLT))
 236     return 0;
 237
 238   if (IS_LSA_MAXAGE (lsa))
 239     ospf_ls_retransmit_add (nbr, lsa);
 240   else
 241     ospf_lsdb_add (&nbr->db_sum, lsa);
 242
 243   return 0;
 244 }
 245
 246 void
 247 ospf_db_summary_clear (struct ospf_neighbor *nbr)
 248 {
 249   struct ospf_lsdb *lsdb;
 250   int i;
 251
 252   lsdb = &nbr->db_sum;
 253   for (i = OSPF_MIN_LSA; i < OSPF_MAX_LSA; i++)
 254     {
 255       struct route_table *table = lsdb->type[i].db;
 256       struct route_node *rn;
 257
 258       for (rn = route_top (table); rn; rn = route_next (rn))
 259         if (rn->info)
 260           ospf_lsdb_delete (&nbr->db_sum, rn->info);
 261     }
 262 }
 263
 264 \f
 265
 266 /* The area link state database consists of the router-LSAs,
 267    network-LSAs and summary-LSAs contained in the area structure,
 268    along with the AS-external-LSAs contained in the global structure.
 269    AS-external-LSAs are omitted from a virtual neighbor's Database
 270    summary list.  AS-external-LSAs are omitted from the Database
 271    summary list if the area has been configured as a stub. */
 272 static int
 273 nsm_negotiation_done (struct ospf_neighbor *nbr)
 274 {
 275   struct ospf_area *area = nbr->oi->area;
 276   struct ospf_lsa *lsa;
 277   struct route_node *rn;
 278
 279   LSDB_LOOP (ROUTER_LSDB (area), rn, lsa)
 280     ospf_db_summary_add (nbr, lsa);
 281   LSDB_LOOP (NETWORK_LSDB (area), rn, lsa)
 282     ospf_db_summary_add (nbr, lsa);
 283   LSDB_LOOP (SUMMARY_LSDB (area), rn, lsa)
 284     ospf_db_summary_add (nbr, lsa);
 285   LSDB_LOOP (ASBR_SUMMARY_LSDB (area), rn, lsa)
 286     ospf_db_summary_add (nbr, lsa);
 287
 288 #ifdef HAVE_OPAQUE_LSA
 289   /* Process only if the neighbor is opaque capable. */
 290   if (CHECK_FLAG (nbr->options, OSPF_OPTION_O))
 291     {
 292       LSDB_LOOP (OPAQUE_LINK_LSDB (area), rn, lsa)
 293         ospf_db_summary_add (nbr, lsa);
 294       LSDB_LOOP (OPAQUE_AREA_LSDB (area), rn, lsa)
 295         ospf_db_summary_add (nbr, lsa);
 296     }
 297 #endif /* HAVE_OPAQUE_LSA */
 298
 299   if (CHECK_FLAG (nbr->options, OSPF_OPTION_NP))
 300     {
 301       LSDB_LOOP (NSSA_LSDB (area), rn, lsa)
 302         ospf_db_summary_add (nbr, lsa);
 303     }
 304
 305   if (nbr->oi->type != OSPF_IFTYPE_VIRTUALLINK
 306       && area->external_routing == OSPF_AREA_DEFAULT)
 307     LSDB_LOOP (EXTERNAL_LSDB (nbr->oi->ospf), rn, lsa)
 308       ospf_db_summary_add (nbr, lsa);
 309
 310 #ifdef HAVE_OPAQUE_LSA
 311   if (CHECK_FLAG (nbr->options, OSPF_OPTION_O)
 312       && (nbr->oi->type != OSPF_IFTYPE_VIRTUALLINK
 313           && area->external_routing == OSPF_AREA_DEFAULT))
 314     LSDB_LOOP (OPAQUE_AS_LSDB (nbr->oi->ospf), rn, lsa)
 315       ospf_db_summary_add (nbr, lsa);
 316 #endif /* HAVE_OPAQUE_LSA */
 317
 318   return 0;
 319 }
 320
 321 static int
 322 nsm_exchange_done (struct ospf_neighbor *nbr)
 323 {
 324   if (ospf_ls_request_isempty (nbr))
 325     return NSM_Full;
 326
 327   /* Send Link State Request. */
 328   ospf_ls_req_send (nbr);
 329
 330   return NSM_Loading;
 331 }
 332
 333 static int
 334 nsm_adj_ok (struct ospf_neighbor *nbr)
 335 {
 336   int next_state = nbr->state;
 337   int adj = nsm_should_adj (nbr);
 338
 339   if (nbr->state == NSM_TwoWay && adj == 1)
 340     next_state = NSM_ExStart;
 341   else if (nbr->state >= NSM_ExStart && adj == 0)
 342     next_state = NSM_TwoWay;
 343
 344   return next_state;
 345 }
 346
 347 /* Clear adjacency related state for a neighbour, intended where nbr
 348  * transitions from > ExStart (i.e. a Full or forming adjacency)
 349  * to <= ExStart.
 350  */
 351 static void
 352 nsm_clear_adj (struct ospf_neighbor *nbr)
 353 {
 354   /* Clear Database Summary list. */
 355   if (!ospf_db_summary_isempty (nbr))
 356     ospf_db_summary_clear (nbr);
 357
 358   /* Clear Link State Request list. */
 359   if (!ospf_ls_request_isempty (nbr))
 360     ospf_ls_request_delete_all (nbr);
 361
 362   /* Clear Link State Retransmission list. */
 363   if (!ospf_ls_retransmit_isempty (nbr))
 364     ospf_ls_retransmit_clear (nbr);
 365
 366 #ifdef HAVE_OPAQUE_LSA
 367   if (CHECK_FLAG (nbr->options, OSPF_OPTION_O))
 368     UNSET_FLAG (nbr->options, OSPF_OPTION_O);
 369 #endif /* HAVE_OPAQUE_LSA */
 370 }
 371
 372 static int
 373 nsm_kill_nbr (struct ospf_neighbor *nbr)
 374 {
 375   /* killing nbr_self is invalid */
 376   if (nbr == nbr->oi->nbr_self)
 377     {
 378       assert (nbr != nbr->oi->nbr_self);
 379       return 0;
 380     }
 381
 382   if (nbr->oi->type == OSPF_IFTYPE_NBMA && nbr->nbr_nbma != NULL)
 383     {
 384       struct ospf_nbr_nbma *nbr_nbma = nbr->nbr_nbma;
 385
 386       nbr_nbma->nbr = NULL;
 387       nbr_nbma->state_change = nbr->state_change;
 388
 389       nbr->nbr_nbma = NULL;
 390
 391       OSPF_POLL_TIMER_ON (nbr_nbma->t_poll, ospf_poll_timer,
 392                           nbr_nbma->v_poll);
 393
 394       if (IS_DEBUG_OSPF (nsm, NSM_EVENTS))
 395         zlog_debug ("NSM[%s:%s]: Down (PollIntervalTimer scheduled)",
 396                    IF_NAME (nbr->oi), inet_ntoa (nbr->address.u.prefix4));
 397     }
 398
 399   return 0;
 400 }
 401
 402 /* Neighbor State Machine */
 403 struct {
 404   int (*func) (struct ospf_neighbor *);
 405   int next_state;
 406 } NSM [OSPF_NSM_STATE_MAX][OSPF_NSM_EVENT_MAX] =
 407 {
 408   {
 409     /* DependUpon: dummy state. */
 410     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 411     { NULL,                    NSM_DependUpon }, /* HelloReceived     */
 412     { NULL,                    NSM_DependUpon }, /* Start             */
 413     { NULL,                    NSM_DependUpon }, /* 2-WayReceived     */
 414     { NULL,                    NSM_DependUpon }, /* NegotiationDone   */
 415     { NULL,                    NSM_DependUpon }, /* ExchangeDone      */
 416     { NULL,                    NSM_DependUpon }, /* BadLSReq          */
 417     { NULL,                    NSM_DependUpon }, /* LoadingDone       */
 418     { NULL,                    NSM_DependUpon }, /* AdjOK?            */
 419     { NULL,                    NSM_DependUpon }, /* SeqNumberMismatch */
 420     { NULL,                    NSM_DependUpon }, /* 1-WayReceived     */
 421     { NULL,                    NSM_DependUpon }, /* KillNbr           */
 422     { NULL,                    NSM_DependUpon }, /* InactivityTimer   */
 423     { NULL,                    NSM_DependUpon }, /* LLDown            */
 424   },
 425   {
 426     /* Deleted: dummy state. */
 427     { NULL,                    NSM_Deleted    }, /* NoEvent           */
 428     { NULL,                    NSM_Deleted    }, /* HelloReceived     */
 429     { NULL,                    NSM_Deleted    }, /* Start             */
 430     { NULL,                    NSM_Deleted    }, /* 2-WayReceived     */
 431     { NULL,                    NSM_Deleted    }, /* NegotiationDone   */
 432     { NULL,                    NSM_Deleted    }, /* ExchangeDone      */
 433     { NULL,                    NSM_Deleted    }, /* BadLSReq          */
 434     { NULL,                    NSM_Deleted    }, /* LoadingDone       */
 435     { NULL,                    NSM_Deleted    }, /* AdjOK?            */
 436     { NULL,                    NSM_Deleted    }, /* SeqNumberMismatch */
 437     { NULL,                    NSM_Deleted    }, /* 1-WayReceived     */
 438     { NULL,                    NSM_Deleted    }, /* KillNbr           */
 439     { NULL,                    NSM_Deleted    }, /* InactivityTimer   */
 440     { NULL,                    NSM_Deleted    }, /* LLDown            */
 441   },
 442   {
 443     /* Down: */
 444     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 445     { nsm_hello_received,      NSM_Init       }, /* HelloReceived     */
 446     { nsm_start,               NSM_Attempt    }, /* Start             */
 447     { NULL,                    NSM_Down       }, /* 2-WayReceived     */
 448     { NULL,                    NSM_Down       }, /* NegotiationDone   */
 449     { NULL,                    NSM_Down       }, /* ExchangeDone      */
 450     { NULL,                    NSM_Down       }, /* BadLSReq          */
 451     { NULL,                    NSM_Down       }, /* LoadingDone       */
 452     { NULL,                    NSM_Down       }, /* AdjOK?            */
 453     { NULL,                    NSM_Down       }, /* SeqNumberMismatch */
 454     { NULL,                    NSM_Down       }, /* 1-WayReceived     */
 455     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 456     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 457     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 458   },
 459   {
 460     /* Attempt: */
 461     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 462     { nsm_hello_received,      NSM_Init       }, /* HelloReceived     */
 463     { NULL,                    NSM_Attempt    }, /* Start             */
 464     { NULL,                    NSM_Attempt    }, /* 2-WayReceived     */
 465     { NULL,                    NSM_Attempt    }, /* NegotiationDone   */
 466     { NULL,                    NSM_Attempt    }, /* ExchangeDone      */
 467     { NULL,                    NSM_Attempt    }, /* BadLSReq          */
 468     { NULL,                    NSM_Attempt    }, /* LoadingDone       */
 469     { NULL,                    NSM_Attempt    }, /* AdjOK?            */
 470     { NULL,                    NSM_Attempt    }, /* SeqNumberMismatch */
 471     { NULL,                    NSM_Attempt    }, /* 1-WayReceived     */
 472     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 473     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 474     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 475   },
 476   {
 477     /* Init: */
 478     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 479     { nsm_hello_received,      NSM_Init       }, /* HelloReceived     */
 480     { NULL,                    NSM_Init       }, /* Start             */
 481     { nsm_twoway_received,     NSM_DependUpon }, /* 2-WayReceived     */
 482     { NULL,                    NSM_Init       }, /* NegotiationDone   */
 483     { NULL,                    NSM_Init       }, /* ExchangeDone      */
 484     { NULL,                    NSM_Init       }, /* BadLSReq          */
 485     { NULL,                    NSM_Init       }, /* LoadingDone       */
 486     { NULL,                    NSM_Init       }, /* AdjOK?            */
 487     { NULL,                    NSM_Init       }, /* SeqNumberMismatch */
 488     { NULL,                    NSM_Init       }, /* 1-WayReceived     */
 489     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 490     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 491     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 492   },
 493   {
 494     /* 2-Way: */
 495     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 496     { nsm_hello_received,      NSM_TwoWay     }, /* HelloReceived     */
 497     { NULL,                    NSM_TwoWay     }, /* Start             */
 498     { NULL,                    NSM_TwoWay     }, /* 2-WayReceived     */
 499     { NULL,                    NSM_TwoWay     }, /* NegotiationDone   */
 500     { NULL,                    NSM_TwoWay     }, /* ExchangeDone      */
 501     { NULL,                    NSM_TwoWay     }, /* BadLSReq          */
 502     { NULL,                    NSM_TwoWay     }, /* LoadingDone       */
 503     { nsm_adj_ok,              NSM_DependUpon }, /* AdjOK?            */
 504     { NULL,                    NSM_TwoWay     }, /* SeqNumberMismatch */
 505     { NULL,                    NSM_Init       }, /* 1-WayReceived     */
 506     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 507     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 508     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 509   },
 510   {
 511     /* ExStart: */
 512     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 513     { nsm_hello_received,      NSM_ExStart    }, /* HelloReceived     */
 514     { NULL,                    NSM_ExStart    }, /* Start             */
 515     { NULL,                    NSM_ExStart    }, /* 2-WayReceived     */
 516     { nsm_negotiation_done,    NSM_Exchange   }, /* NegotiationDone   */
 517     { NULL,                    NSM_ExStart    }, /* ExchangeDone      */
 518     { NULL,                    NSM_ExStart    }, /* BadLSReq          */
 519     { NULL,                    NSM_ExStart    }, /* LoadingDone       */
 520     { nsm_adj_ok,              NSM_DependUpon }, /* AdjOK?            */
 521     { NULL,                    NSM_ExStart    }, /* SeqNumberMismatch */
 522     { NULL,                    NSM_Init       }, /* 1-WayReceived     */
 523     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 524     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 525     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 526   },
 527   {
 528     /* Exchange: */
 529     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 530     { nsm_hello_received,      NSM_Exchange   }, /* HelloReceived     */
 531     { NULL,                    NSM_Exchange   }, /* Start             */
 532     { NULL,                    NSM_Exchange   }, /* 2-WayReceived     */
 533     { NULL,                    NSM_Exchange   }, /* NegotiationDone   */
 534     { nsm_exchange_done,       NSM_DependUpon }, /* ExchangeDone      */
 535     { NULL,                    NSM_ExStart    }, /* BadLSReq          */
 536     { NULL,                    NSM_Exchange   }, /* LoadingDone       */
 537     { nsm_adj_ok,              NSM_DependUpon }, /* AdjOK?            */
 538     { NULL,                    NSM_ExStart    }, /* SeqNumberMismatch */
 539     { NULL,                    NSM_Init       }, /* 1-WayReceived     */
 540     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 541     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 542     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 543   },
 544   {
 545     /* Loading: */
 546     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 547     { nsm_hello_received,      NSM_Loading    }, /* HelloReceived     */
 548     { NULL,                    NSM_Loading    }, /* Start             */
 549     { NULL,                    NSM_Loading    }, /* 2-WayReceived     */
 550     { NULL,                    NSM_Loading    }, /* NegotiationDone   */
 551     { NULL,                    NSM_Loading    }, /* ExchangeDone      */
 552     { NULL,                    NSM_ExStart    }, /* BadLSReq          */
 553     { NULL,                    NSM_Full       }, /* LoadingDone       */
 554     { nsm_adj_ok,              NSM_DependUpon }, /* AdjOK?            */
 555     { NULL,                    NSM_ExStart    }, /* SeqNumberMismatch */
 556     { NULL,                    NSM_Init       }, /* 1-WayReceived     */
 557     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 558     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 559     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 560   },
 561   { /* Full: */
 562     { NULL,                    NSM_DependUpon }, /* NoEvent           */
 563     { nsm_hello_received,      NSM_Full       }, /* HelloReceived     */
 564     { NULL,                    NSM_Full       }, /* Start             */
 565     { NULL,                    NSM_Full       }, /* 2-WayReceived     */
 566     { NULL,                    NSM_Full       }, /* NegotiationDone   */
 567     { NULL,                    NSM_Full       }, /* ExchangeDone      */
 568     { NULL,                    NSM_ExStart    }, /* BadLSReq          */
 569     { NULL,                    NSM_Full       }, /* LoadingDone       */
 570     { nsm_adj_ok,              NSM_DependUpon }, /* AdjOK?            */
 571     { NULL,                    NSM_ExStart    }, /* SeqNumberMismatch */
 572     { NULL,                    NSM_Init       }, /* 1-WayReceived     */
 573     { nsm_kill_nbr,            NSM_Deleted    }, /* KillNbr           */
 574     { nsm_kill_nbr,            NSM_Deleted    }, /* InactivityTimer   */
 575     { nsm_kill_nbr,            NSM_Deleted    }, /* LLDown            */
 576   },
 577 };
 578
 579 const static char *ospf_nsm_event_str[] =
 580 {
 581   "NoEvent",
 582   "HelloReceived",
 583   "Start",
 584   "2-WayReceived",
 585   "NegotiationDone",
 586   "ExchangeDone",
 587   "BadLSReq",
 588   "LoadingDone",
 589   "AdjOK?",
 590   "SeqNumberMismatch",
 591   "1-WayReceived",
 592   "KillNbr",
 593   "InactivityTimer",
 594   "LLDown",
 595 };
 596
 597 static void
 598 nsm_notice_state_change (struct ospf_neighbor *nbr, int next_state, int event)
 599 {
 600   /* Logging change of status. */
 601   if (IS_DEBUG_OSPF (nsm, NSM_STATUS))
 602     zlog_debug ("NSM[%s:%s]: State change %s -> %s (%s)",
 603                IF_NAME (nbr->oi), inet_ntoa (nbr->router_id),
 604                LOOKUP (ospf_nsm_state_msg, nbr->state),
 605                LOOKUP (ospf_nsm_state_msg, next_state),
 606                ospf_nsm_event_str [event]);
 607
 608   /* Optionally notify about adjacency changes */
 609   if (CHECK_FLAG(nbr->oi->ospf->config, OSPF_LOG_ADJACENCY_CHANGES) &&
 610       (CHECK_FLAG(nbr->oi->ospf->config, OSPF_LOG_ADJACENCY_DETAIL) ||
 611        (next_state == NSM_Full) || (next_state < nbr->state)))
 612     zlog_notice("AdjChg: Nbr %s on %s: %s -> %s (%s)",
 613                 inet_ntoa (nbr->router_id), IF_NAME (nbr->oi),
 614                 LOOKUP (ospf_nsm_state_msg, nbr->state),
 615                 LOOKUP (ospf_nsm_state_msg, next_state),
 616                 ospf_nsm_event_str [event]);
 617
 618   /* Advance in NSM */
 619   if (next_state > nbr->state)
 620     nbr->ts_last_progress = recent_relative_time ();
 621   else /* regression in NSM */
 622     {
 623       nbr->ts_last_regress = recent_relative_time ();
 624       nbr->last_regress_str = ospf_nsm_event_str [event];
 625     }
 626
 627 #ifdef HAVE_SNMP
 628   /* Terminal state or regression */
 629   if ((next_state == NSM_Full)
 630       || (next_state == NSM_TwoWay)
 631       || (next_state < nbr->state))
 632     {
 633       /* ospfVirtNbrStateChange */
 634       if (nbr->oi->type == OSPF_IFTYPE_VIRTUALLINK)
 635         ospfTrapVirtNbrStateChange(nbr);
 636       /* ospfNbrStateChange trap  */
 637       else
 638         /* To/From FULL, only managed by DR */
 639         if (((next_state != NSM_Full) && (nbr->state != NSM_Full))
 640             || (nbr->oi->state == ISM_DR))
 641           ospfTrapNbrStateChange(nbr);
 642     }
 643 #endif
 644 }
 645
 646 void
 647 nsm_change_state (struct ospf_neighbor *nbr, int state)
 648 {
 649   struct ospf_interface *oi = nbr->oi;
 650   struct ospf_area *vl_area = NULL;
 651   u_char old_state;
 652   int x;
 653   int force = 1;
 654
 655   /* Preserve old status. */
 656   old_state = nbr->state;
 657
 658   /* Change to new status. */
 659   nbr->state = state;
 660
 661   /* Statistics. */
 662   nbr->state_change++;
 663
 664   if (oi->type == OSPF_IFTYPE_VIRTUALLINK)
 665     vl_area = ospf_area_lookup_by_area_id (oi->ospf, oi->vl_data->vl_area_id);
 666
 667   /* One of the neighboring routers changes to/from the FULL state. */
 668   if ((old_state != NSM_Full && state == NSM_Full) ||
 669       (old_state == NSM_Full && state != NSM_Full))
 670     {
 671       if (state == NSM_Full)
 672         {
 673           oi->full_nbrs++;
 674           oi->area->full_nbrs++;
 675
 676           ospf_check_abr_status (oi->ospf);
 677
 678           if (oi->type == OSPF_IFTYPE_VIRTUALLINK && vl_area)
 679             if (++vl_area->full_vls == 1)
 680               ospf_schedule_abr_task (oi->ospf);
 681
 682           /* kevinm: refresh any redistributions */
 683           for (x = ZEBRA_ROUTE_SYSTEM; x < ZEBRA_ROUTE_MAX; x++)
 684             {
 685               if (x == ZEBRA_ROUTE_OSPF || x == ZEBRA_ROUTE_OSPF6)
 686                 continue;
 687               ospf_external_lsa_refresh_type (oi->ospf, x, force);
 688             }
 689         }
 690       else
 691         {
 692           oi->full_nbrs--;
 693           oi->area->full_nbrs--;
 694
 695           ospf_check_abr_status (oi->ospf);
 696
 697           if (oi->type == OSPF_IFTYPE_VIRTUALLINK && vl_area)
 698             if (vl_area->full_vls > 0)
 699               if (--vl_area->full_vls == 0)
 700                 ospf_schedule_abr_task (oi->ospf);
 701         }
 702
 703       zlog_info ("nsm_change_state(%s, %s -> %s): "
 704                  "scheduling new router-LSA origination",
 705                  inet_ntoa (nbr->router_id),
 706                  LOOKUP(ospf_nsm_state_msg, old_state),
 707                  LOOKUP(ospf_nsm_state_msg, state));
 708
 709       ospf_router_lsa_timer_add (oi->area);
 710
 711       if (oi->type == OSPF_IFTYPE_VIRTUALLINK)
 712         {
 713           struct ospf_area *vl_area =
 714             ospf_area_lookup_by_area_id (oi->ospf, oi->vl_data->vl_area_id);
 715
 716           if (vl_area)
 717             ospf_router_lsa_timer_add (vl_area);
 718         }
 719
 720       /* Originate network-LSA. */
 721       if (oi->state == ISM_DR)
 722         {
 723           if (oi->network_lsa_self && oi->full_nbrs == 0)
 724             {
 725               ospf_lsa_flush_area (oi->network_lsa_self, oi->area);
 726               ospf_lsa_unlock (&oi->network_lsa_self);
 727               oi->network_lsa_self = NULL;
 728               OSPF_TIMER_OFF (oi->t_network_lsa_self);
 729             }
 730           else
 731             ospf_network_lsa_timer_add (oi);
 732         }
 733     }
 734
 735 #ifdef HAVE_OPAQUE_LSA
 736   ospf_opaque_nsm_change (nbr, old_state);
 737 #endif /* HAVE_OPAQUE_LSA */
 738
 739   /* State changes from > ExStart to <= ExStart should clear any Exchange
 740    * or Full/LSA Update related lists and state.
 741    * Potential causal events: BadLSReq, SeqNumberMismatch, AdjOK?
 742    */
 743   if ((old_state > NSM_ExStart) && (state <= NSM_ExStart))
 744     nsm_clear_adj (nbr);
 745
 746   /* Start DD exchange protocol */
 747   if (state == NSM_ExStart)
 748     {
 749       if (nbr->dd_seqnum == 0)
 750         nbr->dd_seqnum = quagga_time (NULL);
 751       else
 752         nbr->dd_seqnum++;
 753
 754       nbr->dd_flags = OSPF_DD_FLAG_I|OSPF_DD_FLAG_M|OSPF_DD_FLAG_MS;
 755       ospf_db_desc_send (nbr);
 756     }
 757
 758   /* clear cryptographic sequence number */
 759   if (state == NSM_Down)
 760     nbr->crypt_seqnum = 0;
 761
 762   /* Generete NeighborChange ISM event. */
 763   switch (oi->state) {
 764   case ISM_DROther:
 765   case ISM_Backup:
 766   case ISM_DR:
 767     if ((old_state < NSM_TwoWay && state >= NSM_TwoWay) ||
 768         (old_state >= NSM_TwoWay && state < NSM_TwoWay))
 769       OSPF_ISM_EVENT_EXECUTE (oi, ISM_NeighborChange);
 770     break;
 771   default:
 772     /* ISM_PointToPoint -> ISM_Down, ISM_Loopback -> ISM_Down, etc. */
 773     break;
 774   }
 775
 776   /* Performance hack. Send hello immideately when some neighbor enter
 777      Init state.  This whay we decrease neighbor discovery time. Gleb.*/
 778   if (state == NSM_Init)
 779     {
 780       OSPF_ISM_TIMER_OFF (oi->t_hello);
 781       OSPF_ISM_TIMER_MSEC_ON (oi->t_hello, ospf_hello_timer, 1);
 782     }
 783
 784   /* Preserve old status? */
 785 }
 786
 787 /* Execute NSM event process. */
 788 int
 789 ospf_nsm_event (struct thread *thread)
 790 {
 791   int event;
 792   int next_state;
 793   struct ospf_neighbor *nbr;
 794   struct in_addr router_id;
 795
 796   nbr = THREAD_ARG (thread);
 797   event = THREAD_VAL (thread);
 798   router_id = nbr->router_id;
 799
 800   if (IS_DEBUG_OSPF (nsm, NSM_EVENTS))
 801     zlog_debug ("NSM[%s:%s]: %s (%s)", IF_NAME (nbr->oi),
 802                inet_ntoa (nbr->router_id),
 803                LOOKUP (ospf_nsm_state_msg, nbr->state),
 804                ospf_nsm_event_str [event]);
 805
 806   next_state = NSM [nbr->state][event].next_state;
 807
 808   /* Call function. */
 809   if (NSM [nbr->state][event].func != NULL)
 810     {
 811       int func_state = (*(NSM [nbr->state][event].func))(nbr);
 812
 813       if (NSM [nbr->state][event].next_state == NSM_DependUpon)
 814         next_state = func_state;
 815       else if (func_state)
 816         {
 817           /* There's a mismatch between the FSM tables and what an FSM
 818            * action/state-change function returned. State changes which
 819            * do not have conditional/DependUpon next-states should not
 820            * try set next_state.
 821            */
 822           zlog_warn ("NSM[%s:%s]: %s (%s): "
 823                      "Warning: action tried to change next_state to %s",
 824                      IF_NAME (nbr->oi), inet_ntoa (nbr->router_id),
 825                      LOOKUP (ospf_nsm_state_msg, nbr->state),
 826                      ospf_nsm_event_str [event],
 827                      LOOKUP (ospf_nsm_state_msg, func_state));
 828         }
 829     }
 830
 831   assert (next_state != NSM_DependUpon);
 832
 833   /* If state is changed. */
 834   if (next_state != nbr->state)
 835     {
 836       nsm_notice_state_change (nbr, next_state, event);
 837       nsm_change_state (nbr, next_state);
 838     }
 839
 840   /* Make sure timer is set. */
 841   nsm_timer_set (nbr);
 842
 843   /* When event is NSM_KillNbr, InactivityTimer or LLDown, the neighbor
 844    * is deleted.
 845    *
 846    * Rather than encode knowledge here of which events lead to NBR
 847    * delete, we take our cue from the NSM table, via the dummy
 848    * 'Deleted' neighbour state.
 849    */
 850   if (nbr->state == NSM_Deleted)
 851     ospf_nbr_delete (nbr);
 852
 853   return 0;
 854 }
 855
 856 /* Check loading state. */
 857 void
 858 ospf_check_nbr_loading (struct ospf_neighbor *nbr)
 859 {
 860   if (nbr->state == NSM_Loading)
 861     {
 862       if (ospf_ls_request_isempty (nbr))
 863         OSPF_NSM_EVENT_SCHEDULE (nbr, NSM_LoadingDone);
 864       else if (nbr->ls_req_last == NULL)
 865         ospf_ls_req_event (nbr);
 866     }
 867 }