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