ospf6d/ospf6_ism.c

   1 /*
   2  * Copyright (C) 1999 Yasuhiro Ohara
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with GNU Zebra; see the file COPYING.  If not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 /* Interface State Machine */
  23
  24 #include "ospf6d.h"
  25
  26 int
  27 ifs_change (state_t ifs_next, char *reason, struct ospf6_interface *o6i)
  28 {
  29   state_t ifs_prev;
  30
  31   ifs_prev = o6i->state;
  32
  33   if (ifs_prev == ifs_next)
  34     return 0;
  35
  36   if (IS_OSPF6_DUMP_INTERFACE)
  37     zlog_info ("I/F: %s: %s -> %s (%s)",
  38                o6i->interface->name,
  39                ospf6_interface_state_string[ifs_prev],
  40                ospf6_interface_state_string[ifs_next], reason);
  41
  42   if ((ifs_prev == IFS_DR || ifs_prev == IFS_BDR) &&
  43       (ifs_next != IFS_DR && ifs_next != IFS_BDR))
  44     ospf6_leave_alldrouters (o6i->interface->ifindex);
  45   else if ((ifs_prev != IFS_DR && ifs_prev != IFS_BDR) &&
  46            (ifs_next == IFS_DR || ifs_next == IFS_BDR))
  47     ospf6_join_alldrouters (o6i->interface->ifindex);
  48
  49   o6i->state = ifs_next;
  50
  51   if (o6i->prevdr != o6i->dr || o6i->prevbdr != o6i->bdr)
  52     {
  53       if (IS_OSPF6_DUMP_INTERFACE)
  54         {
  55           char dr[16], bdr[16], prevdr[16], prevbdr[16];
  56           inet_ntop (AF_INET, &o6i->prevdr, prevdr, sizeof (prevdr));
  57           inet_ntop (AF_INET, &o6i->prevbdr, prevbdr, sizeof (prevbdr));
  58           inet_ntop (AF_INET, &o6i->dr, dr, sizeof (dr));
  59           inet_ntop (AF_INET, &o6i->bdr, bdr, sizeof (bdr));
  60           zlog_info ("I/F: %s: DR: %s -> %s", o6i->interface->name,
  61                      prevdr, dr);
  62           zlog_info ("I/F: %s: BDR: %s -> %s", o6i->interface->name,
  63                      prevbdr, bdr);
  64         }
  65     }
  66
  67   CALL_CHANGE_HOOK (&interface_hook, o6i);
  68   return 0;
  69 }
  70
  71 \f
  72 /* Interface State Machine */
  73 int
  74 interface_up (struct thread *thread)
  75 {
  76   struct ospf6_interface *ospf6_interface;
  77
  78   ospf6_interface = (struct ospf6_interface *)THREAD_ARG (thread);
  79
  80   assert (ospf6_interface);
  81   assert (ospf6_interface->interface);
  82
  83   if (IS_OSPF6_DUMP_INTERFACE)
  84     zlog_info ("I/F: %s: InterfaceUp",
  85                ospf6_interface->interface->name);
  86
  87   /* check physical interface is up */
  88   if (!if_is_up (ospf6_interface->interface))
  89     {
  90       if (IS_OSPF6_DUMP_INTERFACE)
  91         zlog_warn ("  interface %s down, can't execute InterfaceUp",
  92                    ospf6_interface->interface->name);
  93       return -1;
  94     }
  95
  96   /* if already enabled, do nothing */
  97   if (ospf6_interface->state > IFS_DOWN)
  98     {
  99       zlog_warn ("Interface %s already up",
 100                  ospf6_interface->interface->name);
 101       return 0;
 102     }
 103
 104   /* ifid of this interface */
 105   ospf6_interface->if_id = ospf6_interface->interface->ifindex;
 106
 107   /* Join AllSPFRouters */
 108   ospf6_join_allspfrouters (ospf6_interface->interface->ifindex);
 109
 110   /* set socket options */
 111   ospf6_set_reuseaddr ();
 112   ospf6_reset_mcastloop ();
 113   ospf6_set_pktinfo ();
 114   ospf6_set_checksum ();
 115
 116   /* Schedule Hello */
 117   if (! CHECK_FLAG (ospf6_interface->flag, OSPF6_INTERFACE_FLAG_PASSIVE))
 118     thread_add_event (master, ospf6_send_hello, ospf6_interface, 0);
 119
 120   /* decide next interface state */
 121   if (if_is_pointopoint (ospf6_interface->interface))
 122     ifs_change (IFS_PTOP, "IF Type PointToPoint", ospf6_interface);
 123   else if (ospf6_interface->priority == 0)
 124     ifs_change (IFS_DROTHER, "Router Priority = 0", ospf6_interface);
 125   else
 126     {
 127       ifs_change (IFS_WAITING, "Priority > 0", ospf6_interface);
 128       thread_add_timer (master, wait_timer, ospf6_interface,
 129                         ospf6_interface->dead_interval);
 130     }
 131
 132   CALL_FOREACH_LSA_HOOK (hook_interface, hook_change, ospf6_interface);
 133
 134   return 0;
 135 }
 136
 137 int
 138 wait_timer (struct thread *thread)
 139 {
 140   struct ospf6_interface *ospf6_interface;
 141
 142   ospf6_interface = (struct ospf6_interface *)THREAD_ARG  (thread);
 143   assert (ospf6_interface);
 144
 145   if (ospf6_interface->state != IFS_WAITING)
 146     return 0;
 147
 148   if (IS_OSPF6_DUMP_INTERFACE)
 149     zlog_info ("I/F: %s: WaitTimer", ospf6_interface->interface->name);
 150
 151   ifs_change (dr_election (ospf6_interface),
 152               "WaitTimer:DR Election", ospf6_interface);
 153   return 0;
 154 }
 155
 156 int backup_seen (struct thread *thread)
 157 {
 158   struct ospf6_interface *ospf6_interface;
 159
 160   ospf6_interface = (struct ospf6_interface *)THREAD_ARG  (thread);
 161   assert (ospf6_interface);
 162
 163   if (IS_OSPF6_DUMP_INTERFACE)
 164     zlog_info ("I/F: %s: BackupSeen", ospf6_interface->interface->name);
 165
 166   if (ospf6_interface->state == IFS_WAITING)
 167     ifs_change (dr_election (ospf6_interface),
 168                 "BackupSeen:DR Election", ospf6_interface);
 169
 170   return 0;
 171 }
 172
 173 int neighbor_change (struct thread *thread)
 174 {
 175   struct ospf6_interface *ospf6_interface;
 176
 177   ospf6_interface = (struct ospf6_interface *)THREAD_ARG  (thread);
 178   assert (ospf6_interface);
 179
 180   if (ospf6_interface->state != IFS_DROTHER &&
 181       ospf6_interface->state != IFS_BDR &&
 182       ospf6_interface->state != IFS_DR)
 183     return 0;
 184
 185   if (IS_OSPF6_DUMP_INTERFACE)
 186     zlog_info ("I/F: %s: NeighborChange", ospf6_interface->interface->name);
 187
 188   ifs_change (dr_election (ospf6_interface),
 189               "NeighborChange:DR Election", ospf6_interface);
 190
 191   return 0;
 192 }
 193
 194 int
 195 loopind (struct thread *thread)
 196 {
 197   struct ospf6_interface *ospf6_interface;
 198
 199   ospf6_interface = (struct ospf6_interface *)THREAD_ARG (thread);
 200   assert (ospf6_interface);
 201
 202   if (IS_OSPF6_DUMP_INTERFACE)
 203     zlog_info ("I/F: %s: LoopInd", ospf6_interface->interface->name);
 204
 205   /* XXX not yet */
 206
 207   return 0;
 208 }
 209
 210 int
 211 interface_down (struct thread *thread)
 212 {
 213   struct ospf6_interface *ospf6_interface;
 214
 215   ospf6_interface = (struct ospf6_interface *) THREAD_ARG (thread);
 216   assert (ospf6_interface);
 217
 218   if (IS_OSPF6_DUMP_INTERFACE)
 219     zlog_info ("I/F: %s: InterfaceDown", ospf6_interface->interface->name);
 220
 221   if (ospf6_interface->state == IFS_NONE)
 222     return 1;
 223
 224   /* Leave AllSPFRouters */
 225   if (ospf6_interface_is_enabled (ospf6_interface->interface->ifindex))
 226     ospf6_leave_allspfrouters (ospf6_interface->interface->ifindex);
 227
 228   ifs_change (IFS_DOWN, "Configured", ospf6_interface);
 229
 230   return 0;
 231 }
 232
 233 \f
 234 /* 9.4 of RFC2328 */
 235 int
 236 dr_election (struct ospf6_interface *ospf6_interface)
 237 {
 238   list candidate_list = list_new ();
 239   listnode i, j, n;
 240   ifid_t prevdr, prevbdr, dr = 0, bdr;
 241   struct ospf6_neighbor *nbpi, *nbpj, myself, *nbr;
 242   int declare = 0;
 243   int gofive = 0;
 244
 245   /* statistics */
 246   ospf6_interface->ospf6_stat_dr_election++;
 247
 248   /* pseudo neighbor "myself" */
 249   memset (&myself, 0, sizeof (myself));
 250   myself.state = NBS_TWOWAY;
 251   myself.dr = ospf6_interface->dr;
 252   myself.bdr = ospf6_interface->bdr;
 253   myself.priority = ospf6_interface->priority;
 254   myself.ifid = ospf6_interface->if_id;
 255   myself.router_id = ospf6_interface->area->ospf6->router_id;
 256
 257 /* step_one: */
 258
 259   ospf6_interface->prevdr = prevdr = ospf6_interface->dr;
 260   ospf6_interface->prevbdr = prevbdr = ospf6_interface->bdr;
 261
 262 step_two:
 263
 264   /* Calculate Backup Designated Router. */
 265   /* Make Candidate list */
 266   if (!list_isempty (candidate_list))
 267     list_delete_all_node (candidate_list);
 268   declare = 0;
 269   for (i = listhead (ospf6_interface->neighbor_list); i; nextnode (i))
 270     {
 271       nbpi = (struct ospf6_neighbor *)getdata (i);
 272       if (nbpi->priority == 0)
 273         continue;
 274       if (nbpi->state < NBS_TWOWAY)
 275         continue;
 276       if (nbpi->dr == nbpi->router_id)
 277         continue;
 278       if (nbpi->bdr == nbpi->router_id)
 279         declare++;
 280       listnode_add (candidate_list, nbpi);
 281     }
 282
 283   if (myself.priority)
 284     {
 285       if (myself.dr != myself.router_id)
 286         {
 287           if (myself.bdr == myself.router_id)
 288             declare++;
 289           listnode_add (candidate_list, &myself);
 290         }
 291     }
 292
 293   /* Elect BDR */
 294   for (i = listhead (candidate_list);
 295        candidate_list->count > 1;
 296        i = listhead (candidate_list))
 297     {
 298       j = i;
 299       nextnode(j);
 300       assert (j);
 301       nbpi = (struct ospf6_neighbor *)getdata (i);
 302       nbpj = (struct ospf6_neighbor *)getdata (j);
 303       if (declare)
 304         {
 305           int deleted = 0;
 306           if (nbpi->bdr != nbpi->router_id)
 307             {
 308               listnode_delete (candidate_list, nbpi);
 309               deleted++;
 310             }
 311           if (nbpj->bdr != nbpj->router_id)
 312             {
 313               listnode_delete (candidate_list, nbpj);
 314               deleted++;
 315             }
 316           if (deleted)
 317             continue;
 318         }
 319       if (nbpi->priority > nbpj->priority)
 320         {
 321           listnode_delete (candidate_list, nbpj);
 322           continue;
 323         }
 324       else if (nbpi->priority < nbpj->priority)
 325         {
 326           listnode_delete (candidate_list, nbpi);
 327           continue;
 328         }
 329       else /* equal, case of tie */
 330         {
 331           if (ntohl (nbpi->router_id) > ntohl (nbpj->router_id))
 332             {
 333               listnode_delete (candidate_list, nbpj);
 334               continue;
 335             }
 336           else if (ntohl (nbpi->router_id) < ntohl (nbpj->router_id))
 337             {
 338               listnode_delete (candidate_list, nbpi);
 339               continue;
 340             }
 341           else
 342             assert (0);
 343         }
 344     }
 345
 346   if (!list_isempty (candidate_list))
 347     {
 348       assert (candidate_list->count == 1);
 349       n = listhead (candidate_list);
 350       nbr = (struct ospf6_neighbor *)getdata (n);
 351       bdr = nbr->router_id;
 352     }
 353   else
 354     bdr = 0;
 355
 356 /* step_three: */
 357
 358   /* Calculate Designated Router. */
 359   /* Make Candidate list */
 360   if (!list_isempty (candidate_list))
 361     list_delete_all_node (candidate_list);
 362   declare = 0;
 363   for (i = listhead (ospf6_interface->neighbor_list); i; nextnode (i))
 364     {
 365       nbpi = (struct ospf6_neighbor *)getdata (i);
 366       if (nbpi->priority == 0)
 367         continue;
 368       if (nbpi->state < NBS_TWOWAY)
 369         continue;
 370       if (nbpi->dr == nbpi->router_id)
 371         {
 372           declare++;
 373           listnode_add (candidate_list, nbpi);
 374         }
 375     }
 376   if (myself.priority)
 377     {
 378       if (myself.dr == myself.router_id)
 379         {
 380           declare++;
 381           listnode_add (candidate_list, &myself);
 382         }
 383     }
 384
 385   /* Elect DR */
 386   if (declare == 0)
 387     {
 388       assert (list_isempty (candidate_list));
 389       /* No one declare but candidate_list not empty */
 390       dr = bdr;
 391     }
 392   else
 393     {
 394       assert (!list_isempty (candidate_list));
 395       for (i = listhead (candidate_list);
 396            candidate_list->count > 1;
 397            i = listhead (candidate_list))
 398         {
 399           j = i;
 400           nextnode (j);
 401           assert (j);
 402           nbpi = (struct ospf6_neighbor *)getdata (i);
 403           nbpj = (struct ospf6_neighbor *)getdata (j);
 404
 405           if (nbpi->dr != nbpi->router_id)
 406             {
 407               list_delete_node (candidate_list, i);
 408               continue;
 409             }
 410           if (nbpj->dr != nbpj->router_id)
 411             {
 412               list_delete_node (candidate_list, j);
 413               continue;
 414             }
 415
 416           if (nbpi->priority > nbpj->priority)
 417             {
 418               list_delete_node (candidate_list, j);
 419               continue;
 420             }
 421           else if (nbpi->priority < nbpj->priority)
 422             {
 423               list_delete_node (candidate_list, i);
 424               continue;
 425             }
 426           else /* equal, case of tie */
 427             {
 428               if (ntohl (nbpi->router_id) > ntohl (nbpj->router_id))
 429                 {
 430                   list_delete_node (candidate_list, j);
 431                   continue;
 432                 }
 433               else if (ntohl (nbpi->router_id) < ntohl (nbpj->router_id))
 434                 {
 435                   list_delete_node (candidate_list, i);
 436                   continue;
 437                 }
 438               else
 439                 {
 440                   zlog_warn ("!!!THE SAME ROUTER ID FOR DIFFERENT NEIGHBOR");
 441                   zlog_warn ("!!!MISCONFIGURATION?");
 442                   list_delete_node (candidate_list, i);
 443                   continue;
 444                 }
 445             }
 446         }
 447       if (!list_isempty (candidate_list))
 448         {
 449           assert (candidate_list->count == 1);
 450           n = listhead (candidate_list);
 451           nbr = (struct ospf6_neighbor *)getdata (n);
 452           dr = nbr->router_id;
 453         }
 454       else
 455         assert (0);
 456     }
 457
 458 /* step_four: */
 459
 460   if (gofive)
 461     goto step_five;
 462
 463   if (dr != prevdr)
 464     {
 465       if ((dr == myself.router_id || prevdr == myself.router_id)
 466           && !(dr == myself.router_id && prevdr == myself.router_id))
 467         {
 468           myself.dr = dr;
 469           myself.bdr = bdr;
 470           gofive++;
 471           goto step_two;
 472         }
 473     }
 474   if (bdr != prevbdr)
 475     {
 476       if ((bdr == myself.router_id || prevbdr == myself.router_id)
 477           && !(bdr == myself.router_id && prevbdr == myself.router_id))
 478         {
 479           myself.dr = dr;
 480           myself.bdr = bdr;
 481           gofive++;
 482           goto step_two;
 483         }
 484     }
 485
 486 step_five:
 487
 488   ospf6_interface->dr = dr;
 489   ospf6_interface->bdr = bdr;
 490
 491   if (prevdr != dr || prevbdr != bdr)
 492     {
 493       for (i = listhead (ospf6_interface->neighbor_list); i; nextnode (i))
 494         {
 495           nbpi = getdata (i);
 496           if (nbpi->state < NBS_TWOWAY)
 497             continue;
 498           /* Schedule or Execute AdjOK. which does "invoke" mean? */
 499           thread_add_event (master, adj_ok, nbpi, 0);
 500         }
 501     }
 502
 503   list_delete (candidate_list);
 504
 505   if (dr == myself.router_id)
 506     {
 507       assert (bdr != myself.router_id);
 508       return IFS_DR;
 509     }
 510   else if (bdr == myself.router_id)
 511     {
 512       assert (dr != myself.router_id);
 513       return IFS_BDR;
 514     }
 515   else
 516     return IFS_DROTHER;
 517 }
 518
 519