ospfd/ospf_spf.c

   1 /* OSPF SPF calculation.
   2    Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
   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 Free
  18 Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.  */
  20
  21 #include <zebra.h>
  22
  23 #include "thread.h"
  24 #include "memory.h"
  25 #include "hash.h"
  26 #include "linklist.h"
  27 #include "prefix.h"
  28 #include "if.h"
  29 #include "table.h"
  30 #include "log.h"
  31 #include "sockunion.h"          /* for inet_ntop () */
  32 #include "pqueue.h"
  33
  34 #include "ospfd/ospfd.h"
  35 #include "ospfd/ospf_interface.h"
  36 #include "ospfd/ospf_ism.h"
  37 #include "ospfd/ospf_asbr.h"
  38 #include "ospfd/ospf_lsa.h"
  39 #include "ospfd/ospf_lsdb.h"
  40 #include "ospfd/ospf_neighbor.h"
  41 #include "ospfd/ospf_nsm.h"
  42 #include "ospfd/ospf_spf.h"
  43 #include "ospfd/ospf_route.h"
  44 #include "ospfd/ospf_ia.h"
  45 #include "ospfd/ospf_ase.h"
  46 #include "ospfd/ospf_abr.h"
  47 #include "ospfd/ospf_dump.h"
  48
  49 /* Variables to ensure a SPF scheduled log message is printed only once */
  50
  51 static unsigned int spf_reason_flags = 0;
  52
  53 static void
  54 ospf_clear_spf_reason_flags ()
  55 {
  56   spf_reason_flags = 0;
  57 }
  58
  59 static void
  60 ospf_spf_set_reason (ospf_spf_reason_t reason)
  61 {
  62   spf_reason_flags |= 1 << reason;
  63 }
  64
  65 static void
  66 ospf_get_spf_reason_str (char *buf)
  67 {
  68   if (!buf)
  69    return;
  70
  71   buf[0] = '\0';
  72   if (spf_reason_flags)
  73     {
  74       if (spf_reason_flags & SPF_FLAG_ROUTER_LSA_INSTALL)
  75         strcat (buf, "R, ");
  76       if (spf_reason_flags & SPF_FLAG_NETWORK_LSA_INSTALL)
  77         strcat (buf, "N, ");
  78       if (spf_reason_flags & SPF_FLAG_SUMMARY_LSA_INSTALL)
  79         strcat (buf, "S, ");
  80       if (spf_reason_flags & SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL)
  81         strcat (buf, "AS, ");
  82       if (spf_reason_flags & SPF_FLAG_ABR_STATUS_CHANGE)
  83         strcat (buf, "ABR, ");
  84       if (spf_reason_flags & SPF_FLAG_ASBR_STATUS_CHANGE)
  85         strcat (buf, "ASBR, ");
  86       if (spf_reason_flags & SPF_FLAG_MAXAGE)
  87         strcat (buf, "M, ");
  88       buf[strlen(buf)-2] = '\0'; /* skip the last ", " */
  89     }
  90 }
  91
  92 static void ospf_vertex_free (void *);
  93 /* List of allocated vertices, to simplify cleanup of SPF.
  94  * Not thread-safe obviously. If it ever needs to be, it'd have to be
  95  * dynamically allocated at begin of ospf_spf_calculate
  96  */
  97 static struct list vertex_list = { .del = ospf_vertex_free };
  98
  99 /* Heap related functions, for the managment of the candidates, to
 100  * be used with pqueue. */
 101 static int
 102 cmp (void * node1 , void * node2)
 103 {
 104   struct vertex * v1 = (struct vertex *) node1;
 105   struct vertex * v2 = (struct vertex *) node2;
 106   if (v1 != NULL && v2 != NULL )
 107     {
 108       /* network vertices must be chosen before router vertices of same
 109        * cost in order to find all shortest paths
 110        */
 111       if ( ((v1->distance - v2->distance) == 0)
 112           && (v1->type != v2->type))
 113         {
 114           switch (v1->type)
 115             {
 116               case OSPF_VERTEX_NETWORK:
 117                 return -1;
 118               case OSPF_VERTEX_ROUTER:
 119                 return 1;
 120             }
 121         }
 122       else
 123         return (v1->distance - v2->distance);
 124     }
 125   return 0;
 126 }
 127
 128 static void
 129 update_stat (void *node , int position)
 130 {
 131   struct vertex *v = node;
 132
 133   /* Set the status of the vertex, when its position changes. */
 134   *(v->stat) = position;
 135 }
 136
 137 static struct vertex_nexthop *
 138 vertex_nexthop_new (void)
 139 {
 140   return XCALLOC (MTYPE_OSPF_NEXTHOP, sizeof (struct vertex_nexthop));
 141 }
 142
 143 static void
 144 vertex_nexthop_free (struct vertex_nexthop *nh)
 145 {
 146   XFREE (MTYPE_OSPF_NEXTHOP, nh);
 147 }
 148
 149 /* Free the canonical nexthop objects for an area, ie the nexthop objects
 150  * attached to the first-hop router vertices, and any intervening network
 151  * vertices.
 152  */
 153 static void
 154 ospf_canonical_nexthops_free (struct vertex *root)
 155 {
 156   struct listnode *node, *nnode;
 157   struct vertex *child;
 158
 159   for (ALL_LIST_ELEMENTS (root->children, node, nnode, child))
 160     {
 161       struct listnode *n2, *nn2;
 162       struct vertex_parent *vp;
 163
 164       /* router vertices through an attached network each
 165        * have a distinct (canonical / not inherited) nexthop
 166        * which must be freed.
 167        *
 168        * A network vertex can only have router vertices as its
 169        * children, so only one level of recursion is possible.
 170        */
 171       if (child->type == OSPF_VERTEX_NETWORK)
 172         ospf_canonical_nexthops_free (child);
 173
 174       /* Free child nexthops pointing back to this root vertex */
 175       for (ALL_LIST_ELEMENTS (child->parents, n2, nn2, vp))
 176         if (vp->parent == root && vp->nexthop)
 177           vertex_nexthop_free (vp->nexthop);
 178     }
 179 }
 180
 181 /* TODO: Parent list should be excised, in favour of maintaining only
 182  * vertex_nexthop, with refcounts.
 183  */
 184 static struct vertex_parent *
 185 vertex_parent_new (struct vertex *v, int backlink, struct vertex_nexthop *hop)
 186 {
 187   struct vertex_parent *new;
 188
 189   new = XMALLOC (MTYPE_OSPF_VERTEX_PARENT, sizeof (struct vertex_parent));
 190
 191   if (new == NULL)
 192     return NULL;
 193
 194   new->parent = v;
 195   new->backlink = backlink;
 196   new->nexthop = hop;
 197   return new;
 198 }
 199
 200 static void
 201 vertex_parent_free (void *p)
 202 {
 203   XFREE (MTYPE_OSPF_VERTEX_PARENT, p);
 204 }
 205
 206 static struct vertex *
 207 ospf_vertex_new (struct ospf_lsa *lsa)
 208 {
 209   struct vertex *new;
 210
 211   new = XCALLOC (MTYPE_OSPF_VERTEX, sizeof (struct vertex));
 212
 213   new->flags = 0;
 214   new->stat = &(lsa->stat);
 215   new->type = lsa->data->type;
 216   new->id = lsa->data->id;
 217   new->lsa = lsa->data;
 218   new->children = list_new ();
 219   new->parents = list_new ();
 220   new->parents->del = vertex_parent_free;
 221
 222   listnode_add (&vertex_list, new);
 223
 224   if (IS_DEBUG_OSPF_EVENT)
 225     zlog_debug ("%s: Created %s vertex %s", __func__,
 226                 new->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
 227                 inet_ntoa (new->lsa->id));
 228   return new;
 229 }
 230
 231 static void
 232 ospf_vertex_free (void *data)
 233 {
 234   struct vertex *v = data;
 235
 236   if (IS_DEBUG_OSPF_EVENT)
 237     zlog_debug ("%s: Free %s vertex %s", __func__,
 238                 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
 239                 inet_ntoa (v->lsa->id));
 240
 241   /* There should be no parents potentially holding references to this vertex
 242    * Children however may still be there, but presumably referenced by other
 243    * vertices
 244    */
 245   //assert (listcount (v->parents) == 0);
 246
 247   if (v->children)
 248     list_delete (v->children);
 249   v->children = NULL;
 250
 251   if (v->parents)
 252     list_delete (v->parents);
 253   v->parents = NULL;
 254
 255   v->lsa = NULL;
 256
 257   XFREE (MTYPE_OSPF_VERTEX, v);
 258 }
 259
 260 static void
 261 ospf_vertex_dump(const char *msg, struct vertex *v,
 262                  int print_parents, int print_children)
 263 {
 264   if ( ! IS_DEBUG_OSPF_EVENT)
 265     return;
 266
 267   zlog_debug("%s %s vertex %s  distance %u flags %u",
 268             msg,
 269             v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
 270             inet_ntoa(v->lsa->id),
 271             v->distance,
 272             (unsigned int)v->flags);
 273
 274   if (print_parents)
 275     {
 276       struct listnode *node;
 277       struct vertex_parent *vp;
 278
 279       for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
 280         {
 281           char buf1[BUFSIZ];
 282
 283           if (vp)
 284             {
 285               zlog_debug ("parent %s backlink %d nexthop %s  interface %s",
 286                          inet_ntoa(vp->parent->lsa->id), vp->backlink,
 287                          inet_ntop(AF_INET, &vp->nexthop->router, buf1, BUFSIZ),
 288                          vp->nexthop->oi ? IF_NAME(vp->nexthop->oi) : "NULL");
 289             }
 290         }
 291     }
 292
 293   if (print_children)
 294     {
 295       struct listnode *cnode;
 296       struct vertex *cv;
 297
 298       for (ALL_LIST_ELEMENTS_RO (v->children, cnode, cv))
 299         ospf_vertex_dump(" child:", cv, 0, 0);
 300     }
 301 }
 302
 303
 304 /* Add a vertex to the list of children in each of its parents. */
 305 static void
 306 ospf_vertex_add_parent (struct vertex *v)
 307 {
 308   struct vertex_parent *vp;
 309   struct listnode *node;
 310
 311   assert (v && v->parents);
 312
 313   for (ALL_LIST_ELEMENTS_RO (v->parents, node, vp))
 314     {
 315       assert (vp->parent && vp->parent->children);
 316
 317       /* No need to add two links from the same parent. */
 318       if (listnode_lookup (vp->parent->children, v) == NULL)
 319         listnode_add (vp->parent->children, v);
 320     }
 321 }
 322
 323 static void
 324 ospf_spf_init (struct ospf_area *area)
 325 {
 326   struct vertex *v;
 327
 328   /* Create root node. */
 329   v = ospf_vertex_new (area->router_lsa_self);
 330
 331   area->spf = v;
 332
 333   /* Reset ABR and ASBR router counts. */
 334   area->abr_count = 0;
 335   area->asbr_count = 0;
 336 }
 337
 338 /* return index of link back to V from W, or -1 if no link found */
 339 static int
 340 ospf_lsa_has_link (struct lsa_header *w, struct lsa_header *v)
 341 {
 342   unsigned int i, length;
 343   struct router_lsa *rl;
 344   struct network_lsa *nl;
 345
 346   /* In case of W is Network LSA. */
 347   if (w->type == OSPF_NETWORK_LSA)
 348     {
 349       if (v->type == OSPF_NETWORK_LSA)
 350         return -1;
 351
 352       nl = (struct network_lsa *) w;
 353       length = (ntohs (w->length) - OSPF_LSA_HEADER_SIZE - 4) / 4;
 354
 355       for (i = 0; i < length; i++)
 356         if (IPV4_ADDR_SAME (&nl->routers[i], &v->id))
 357           return i;
 358       return -1;
 359     }
 360
 361   /* In case of W is Router LSA. */
 362   if (w->type == OSPF_ROUTER_LSA)
 363     {
 364       rl = (struct router_lsa *) w;
 365
 366       length = ntohs (w->length);
 367
 368       for (i = 0;
 369            i < ntohs (rl->links) && length >= sizeof (struct router_lsa);
 370            i++, length -= 12)
 371         {
 372           switch (rl->link[i].type)
 373             {
 374             case LSA_LINK_TYPE_POINTOPOINT:
 375             case LSA_LINK_TYPE_VIRTUALLINK:
 376               /* Router LSA ID. */
 377               if (v->type == OSPF_ROUTER_LSA &&
 378                   IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
 379                 {
 380                   return i;
 381                 }
 382               break;
 383             case LSA_LINK_TYPE_TRANSIT:
 384               /* Network LSA ID. */
 385               if (v->type == OSPF_NETWORK_LSA &&
 386                   IPV4_ADDR_SAME (&rl->link[i].link_id, &v->id))
 387                 {
 388                   return i;
 389                 }
 390               break;
 391             case LSA_LINK_TYPE_STUB:
 392               /* Stub can't lead anywhere, carry on */
 393               continue;
 394             default:
 395               break;
 396             }
 397         }
 398     }
 399   return -1;
 400 }
 401
 402 /* Find the next link after prev_link from v to w.  If prev_link is
 403  * NULL, return the first link from v to w.  Ignore stub and virtual links;
 404  * these link types will never be returned.
 405  */
 406 static struct router_lsa_link *
 407 ospf_get_next_link (struct vertex *v, struct vertex *w,
 408                     struct router_lsa_link *prev_link)
 409 {
 410   u_char *p;
 411   u_char *lim;
 412   u_char lsa_type =  LSA_LINK_TYPE_TRANSIT;
 413   struct router_lsa_link *l;
 414
 415   if (w->type == OSPF_VERTEX_ROUTER)
 416     lsa_type = LSA_LINK_TYPE_POINTOPOINT;
 417
 418   if (prev_link == NULL)
 419     p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
 420   else
 421     {
 422       p = (u_char *) prev_link;
 423       p += (OSPF_ROUTER_LSA_LINK_SIZE +
 424             (prev_link->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
 425     }
 426
 427   lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
 428
 429   while (p < lim)
 430     {
 431       l = (struct router_lsa_link *) p;
 432
 433       p += (OSPF_ROUTER_LSA_LINK_SIZE + (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
 434
 435       if (l->m[0].type != lsa_type)
 436         continue;
 437
 438       if (IPV4_ADDR_SAME (&l->link_id, &w->id))
 439         return l;
 440     }
 441
 442   return NULL;
 443 }
 444
 445 static void
 446 ospf_spf_flush_parents (struct vertex *w)
 447 {
 448   struct vertex_parent *vp;
 449   struct listnode *ln, *nn;
 450
 451   /* delete the existing nexthops */
 452   for (ALL_LIST_ELEMENTS (w->parents, ln, nn, vp))
 453     {
 454       list_delete_node (w->parents, ln);
 455       vertex_parent_free (vp);
 456     }
 457 }
 458
 459 /*
 460  * Consider supplied next-hop for inclusion to the supplied list of
 461  * equal-cost next-hops, adjust list as neccessary.
 462  */
 463 static void
 464 ospf_spf_add_parent (struct vertex *v, struct vertex *w,
 465                      struct vertex_nexthop *newhop,
 466                      unsigned int distance)
 467 {
 468   struct vertex_parent *vp, *wp;
 469   struct listnode *node;
 470
 471   /* we must have a newhop, and a distance */
 472   assert (v && w && newhop);
 473   assert (distance);
 474
 475   /* IFF w has already been assigned a distance, then we shouldn't get here
 476    * unless callers have determined V(l)->W is shortest / equal-shortest
 477    * path (0 is a special case distance (no distance yet assigned)).
 478    */
 479   if (w->distance)
 480     assert (distance <= w->distance);
 481   else
 482     w->distance = distance;
 483
 484   if (IS_DEBUG_OSPF_EVENT)
 485     {
 486       char buf[2][INET_ADDRSTRLEN];
 487       zlog_debug ("%s: Adding %s as parent of %s",
 488                 __func__,
 489                 inet_ntop(AF_INET, &v->lsa->id, buf[0], sizeof(buf[0])),
 490                 inet_ntop(AF_INET, &w->lsa->id, buf[1], sizeof(buf[1])));
 491     }
 492
 493   /* Adding parent for a new, better path: flush existing parents from W. */
 494   if (distance < w->distance)
 495     {
 496       if (IS_DEBUG_OSPF_EVENT)
 497         zlog_debug ("%s: distance %d better than %d, flushing existing parents",
 498                     __func__, distance, w->distance);
 499       ospf_spf_flush_parents (w);
 500       w->distance = distance;
 501     }
 502
 503   /* new parent is <= existing parents, add it to parent list (if nexthop
 504    * not on parent list)
 505    */
 506   for (ALL_LIST_ELEMENTS_RO(w->parents, node, wp))
 507     {
 508       if (memcmp(newhop, wp->nexthop, sizeof(*newhop)) == 0)
 509         {
 510           if (IS_DEBUG_OSPF_EVENT)
 511             zlog_debug ("%s: ... nexthop already on parent list, skipping add", __func__);
 512           return;
 513         }
 514     }
 515
 516   vp = vertex_parent_new (v, ospf_lsa_has_link (w->lsa, v->lsa), newhop);
 517   listnode_add (w->parents, vp);
 518
 519   return;
 520 }
 521
 522 /* 16.1.1.  Calculate nexthop from root through V (parent) to
 523  * vertex W (destination), with given distance from root->W.
 524  *
 525  * The link must be supplied if V is the root vertex. In all other cases
 526  * it may be NULL.
 527  *
 528  * Note that this function may fail, hence the state of the destination
 529  * vertex, W, should /not/ be modified in a dependent manner until
 530  * this function returns. This function will update the W vertex with the
 531  * provided distance as appropriate.
 532  */
 533 static unsigned int
 534 ospf_nexthop_calculation (struct ospf_area *area, struct vertex *v,
 535                           struct vertex *w, struct router_lsa_link *l,
 536                           unsigned int distance, int lsa_pos)
 537 {
 538   struct listnode *node, *nnode;
 539   struct vertex_nexthop *nh;
 540   struct vertex_parent *vp;
 541   struct ospf_interface *oi = NULL;
 542   unsigned int added = 0;
 543   char buf1[BUFSIZ];
 544   char buf2[BUFSIZ];
 545
 546   if (IS_DEBUG_OSPF_EVENT)
 547     {
 548       zlog_debug ("ospf_nexthop_calculation(): Start");
 549       ospf_vertex_dump("V (parent):", v, 1, 1);
 550       ospf_vertex_dump("W (dest)  :", w, 1, 1);
 551       zlog_debug ("V->W distance: %d", distance);
 552     }
 553
 554   if (v == area->spf)
 555     {
 556       /* 16.1.1 para 4.  In the first case, the parent vertex (V) is the
 557          root (the calculating router itself).  This means that the
 558          destination is either a directly connected network or directly
 559          connected router.  The outgoing interface in this case is simply
 560          the OSPF interface connecting to the destination network/router.
 561       */
 562
 563       /* we *must* be supplied with the link data */
 564       assert (l != NULL);
 565       oi = ospf_if_lookup_by_lsa_pos (area, lsa_pos);
 566       if (!oi)
 567         {
 568           zlog_debug("%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
 569                      __func__, lsa_pos,
 570                      inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
 571                      inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
 572           return 0;
 573         }
 574
 575       if (IS_DEBUG_OSPF_EVENT)
 576         {
 577           zlog_debug("%s: considering link:%s "
 578                      "type:%d link_id:%s link_data:%s",
 579                      __func__, oi->ifp->name, l->m[0].type,
 580                      inet_ntop (AF_INET, &l->link_id, buf1, BUFSIZ),
 581                      inet_ntop (AF_INET, &l->link_data, buf2, BUFSIZ));
 582         }
 583
 584       if (w->type == OSPF_VERTEX_ROUTER)
 585         {
 586           /* l  is a link from v to w
 587            * l2 will be link from w to v
 588            */
 589           struct router_lsa_link *l2 = NULL;
 590
 591           if (l->m[0].type == LSA_LINK_TYPE_POINTOPOINT)
 592             {
 593               struct in_addr nexthop = { .s_addr = 0 };
 594
 595               /* If the destination is a router which connects to
 596                  the calculating router via a Point-to-MultiPoint
 597                  network, the destination's next hop IP address(es)
 598                  can be determined by examining the destination's
 599                  router-LSA: each link pointing back to the
 600                  calculating router and having a Link Data field
 601                  belonging to the Point-to-MultiPoint network
 602                  provides an IP address of the next hop router.
 603
 604                  At this point l is a link from V to W, and V is the
 605                  root ("us"). If it is a point-to-multipoint interface,
 606                  then look through the links in the opposite direction (W to V).
 607                  If any of them have an address that lands within the
 608                  subnet declared by the PtMP link, then that link
 609                  is a constituent of the PtMP link, and its address is
 610                  a nexthop address for V.
 611               */
 612               if (oi->type == OSPF_IFTYPE_POINTOPOINT)
 613                 {
 614                   /* Having nexthop = 0 is tempting, but NOT acceptable.
 615                      It breaks AS-External routes with a forwarding address,
 616                      since ospf_ase_complete_direct_routes() will mistakenly
 617                      assume we've reached the last hop and should place the
 618                      forwarding address as nexthop.
 619                      Also, users may configure multi-access links in p2p mode,
 620                      so we need the IP to ARP the nexthop.
 621                   */
 622                   struct ospf_neighbor *nbr_w;
 623
 624                   nbr_w = ospf_nbr_lookup_by_routerid (oi->nbrs, &l->link_id);
 625                   if (nbr_w != NULL)
 626                     {
 627                       added = 1;
 628                       nexthop = nbr_w->src;
 629                     }
 630                 }
 631               else if (oi->type == OSPF_IFTYPE_POINTOMULTIPOINT)
 632                 {
 633                   struct prefix_ipv4 la;
 634
 635                   la.family = AF_INET;
 636                   la.prefixlen = oi->address->prefixlen;
 637
 638                   /* V links to W on PtMP interface
 639                      - find the interface address on W */
 640                   while ((l2 = ospf_get_next_link (w, v, l2)))
 641                     {
 642                       la.prefix = l2->link_data;
 643
 644                       if (prefix_cmp ((struct prefix *) &la,
 645                                       oi->address) != 0)
 646                         continue;
 647                       /* link_data is on our PtMP network */
 648                       added = 1;
 649                       nexthop = l2->link_data;
 650                       break;
 651                     }
 652                 }
 653
 654               if (added)
 655                 {
 656                   /* found all necessary info to build nexthop */
 657                   nh = vertex_nexthop_new ();
 658                   nh->oi = oi;
 659                   nh->router = nexthop;
 660                   ospf_spf_add_parent (v, w, nh, distance);
 661                   return 1;
 662                 }
 663               else
 664                 zlog_info("%s: could not determine nexthop for link %s",
 665                           __func__, oi->ifp->name);
 666             } /* end point-to-point link from V to W */
 667           else if (l->m[0].type == LSA_LINK_TYPE_VIRTUALLINK)
 668             {
 669               struct ospf_vl_data *vl_data;
 670
 671               /* VLink implementation limitations:
 672                * a) vl_data can only reference one nexthop, so no ECMP
 673                *    to backbone through VLinks. Though transit-area
 674                *    summaries may be considered, and those can be ECMP.
 675                * b) We can only use /one/ VLink, even if multiple ones
 676                *    exist this router through multiple transit-areas.
 677                */
 678               vl_data = ospf_vl_lookup (area->ospf, NULL, l->link_id);
 679
 680               if (vl_data
 681                   && CHECK_FLAG (vl_data->flags, OSPF_VL_FLAG_APPROVED))
 682                 {
 683                   nh = vertex_nexthop_new ();
 684                   nh->oi = vl_data->nexthop.oi;
 685                   nh->router = vl_data->nexthop.router;
 686                   ospf_spf_add_parent (v, w, nh, distance);
 687                   return 1;
 688                 }
 689               else
 690                   zlog_info("ospf_nexthop_calculation(): "
 691                             "vl_data for VL link not found");
 692             } /* end virtual-link from V to W */
 693           return 0;
 694         } /* end W is a Router vertex */
 695       else
 696         {
 697           assert(w->type == OSPF_VERTEX_NETWORK);
 698
 699           nh = vertex_nexthop_new ();
 700           nh->oi = oi;
 701           nh->router.s_addr = 0; /* Nexthop not required */
 702           ospf_spf_add_parent (v, w, nh, distance);
 703           return 1;
 704         }
 705     } /* end V is the root */
 706   /* Check if W's parent is a network connected to root. */
 707   else if (v->type == OSPF_VERTEX_NETWORK)
 708     {
 709       /* See if any of V's parents are the root. */
 710       for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
 711         {
 712           if (vp->parent == area->spf) /* connects to root? */
 713             {
 714               /* 16.1.1 para 5. ...the parent vertex is a network that
 715                * directly connects the calculating router to the destination
 716                * router.  The list of next hops is then determined by
 717                * examining the destination's router-LSA...
 718                */
 719
 720               assert(w->type == OSPF_VERTEX_ROUTER);
 721               while ((l = ospf_get_next_link (w, v, l)))
 722                 {
 723                   /* ...For each link in the router-LSA that points back to the
 724                    * parent network, the link's Link Data field provides the IP
 725                    * address of a next hop router.  The outgoing interface to
 726                    * use can then be derived from the next hop IP address (or
 727                    * it can be inherited from the parent network).
 728                    */
 729                   nh = vertex_nexthop_new ();
 730                   nh->oi = vp->nexthop->oi;
 731                   nh->router = l->link_data;
 732                   added = 1;
 733                   ospf_spf_add_parent (v, w, nh, distance);
 734                 }
 735               /* Note lack of return is deliberate. See next comment. */
 736           }
 737         }
 738       /* NB: This code is non-trivial.
 739        *
 740        * E.g. it is not enough to know that V connects to the root. It is
 741        * also important that the while above, looping through all links from
 742        * W->V found at least one link, so that we know there is
 743        * bi-directional connectivity between V and W (which need not be the
 744        * case, e.g.  when OSPF has not yet converged fully).  Otherwise, if
 745        * we /always/ return here, without having checked that root->V->-W
 746        * actually resulted in a valid nexthop being created, then we we will
 747        * prevent SPF from finding/using higher cost paths.
 748        *
 749        * It is important, if root->V->W has not been added, that we continue
 750        * through to the intervening-router nexthop code below.  So as to
 751        * ensure other paths to V may be used.  This avoids unnecessary
 752        * blackholes while OSPF is convergening.
 753        *
 754        * I.e. we may have arrived at this function, examining V -> W, via
 755        * workable paths other than root -> V, and it's important to avoid
 756        * getting "confused" by non-working root->V->W path - it's important
 757        * to *not* lose the working non-root paths, just because of a
 758        * non-viable root->V->W.
 759        *
 760        * See also bug #330 (required reading!), and:
 761        *
 762        * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
 763        */
 764       if (added)
 765         return added;
 766     }
 767
 768   /* 16.1.1 para 4.  If there is at least one intervening router in the
 769    * current shortest path between the destination and the root, the
 770    * destination simply inherits the set of next hops from the
 771    * parent.
 772    */
 773   if (IS_DEBUG_OSPF_EVENT)
 774     zlog_debug ("%s: Intervening routers, adding parent(s)", __func__);
 775
 776   for (ALL_LIST_ELEMENTS (v->parents, node, nnode, vp))
 777     {
 778       added = 1;
 779       ospf_spf_add_parent (v, w, vp->nexthop, distance);
 780     }
 781
 782   return added;
 783 }
 784
 785 /* RFC2328 Section 16.1 (2).
 786  * v is on the SPF tree.  Examine the links in v's LSA.  Update the list
 787  * of candidates with any vertices not already on the list.  If a lower-cost
 788  * path is found to a vertex already on the candidate list, store the new cost.
 789  */
 790 static void
 791 ospf_spf_next (struct vertex *v, struct ospf_area *area,
 792                struct pqueue * candidate)
 793 {
 794   struct ospf_lsa *w_lsa = NULL;
 795   u_char *p;
 796   u_char *lim;
 797   struct router_lsa_link *l = NULL;
 798   struct in_addr *r;
 799   int type = 0, lsa_pos=-1, lsa_pos_next=0;
 800
 801   /* If this is a router-LSA, and bit V of the router-LSA (see Section
 802      A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE.  */
 803   if (v->type == OSPF_VERTEX_ROUTER)
 804     {
 805       if (IS_ROUTER_LSA_VIRTUAL ((struct router_lsa *) v->lsa))
 806         area->transit = OSPF_TRANSIT_TRUE;
 807     }
 808
 809   if (IS_DEBUG_OSPF_EVENT)
 810     zlog_debug ("%s: Next vertex of %s vertex %s",
 811                 __func__,
 812                 v->type == OSPF_VERTEX_ROUTER ? "Router" : "Network",
 813                 inet_ntoa(v->lsa->id));
 814
 815   p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
 816   lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
 817
 818   while (p < lim)
 819     {
 820       struct vertex *w;
 821       unsigned int distance;
 822
 823       /* In case of V is Router-LSA. */
 824       if (v->lsa->type == OSPF_ROUTER_LSA)
 825         {
 826           l = (struct router_lsa_link *) p;
 827
 828           lsa_pos = lsa_pos_next; /* LSA link position */
 829           lsa_pos_next++;
 830           p += (OSPF_ROUTER_LSA_LINK_SIZE +
 831                 (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
 832
 833           /* (a) If this is a link to a stub network, examine the next
 834              link in V's LSA.  Links to stub networks will be
 835              considered in the second stage of the shortest path
 836              calculation. */
 837           if ((type = l->m[0].type) == LSA_LINK_TYPE_STUB)
 838             continue;
 839
 840           /* Infinite distance links shouldn't be followed, except
 841            * for local links (a stub-routed router still wants to
 842            * calculate tree, so must follow its own links).
 843            */
 844           if ((v != area->spf) && l->m[0].metric >= OSPF_OUTPUT_COST_INFINITE)
 845             continue;
 846
 847           /* (b) Otherwise, W is a transit vertex (router or transit
 848              network).  Look up the vertex W's LSA (router-LSA or
 849              network-LSA) in Area A's link state database. */
 850           switch (type)
 851             {
 852             case LSA_LINK_TYPE_POINTOPOINT:
 853             case LSA_LINK_TYPE_VIRTUALLINK:
 854               if (type == LSA_LINK_TYPE_VIRTUALLINK)
 855                 {
 856                   if (IS_DEBUG_OSPF_EVENT)
 857                     zlog_debug ("looking up LSA through VL: %s",
 858                                inet_ntoa (l->link_id));
 859                 }
 860
 861               w_lsa = ospf_lsa_lookup (area, OSPF_ROUTER_LSA, l->link_id,
 862                                        l->link_id);
 863               if (w_lsa)
 864                 {
 865                   if (IS_DEBUG_OSPF_EVENT)
 866                     zlog_debug ("found Router LSA %s", inet_ntoa (l->link_id));
 867                 }
 868               break;
 869             case LSA_LINK_TYPE_TRANSIT:
 870               if (IS_DEBUG_OSPF_EVENT)
 871                 zlog_debug ("Looking up Network LSA, ID: %s",
 872                            inet_ntoa (l->link_id));
 873               w_lsa = ospf_lsa_lookup_by_id (area, OSPF_NETWORK_LSA,
 874                                              l->link_id);
 875               if (w_lsa)
 876                 if (IS_DEBUG_OSPF_EVENT)
 877                   zlog_debug ("found the LSA");
 878               break;
 879             default:
 880               zlog_warn ("Invalid LSA link type %d", type);
 881               continue;
 882             }
 883         }
 884       else
 885         {
 886           /* In case of V is Network-LSA. */
 887           r = (struct in_addr *) p;
 888           p += sizeof (struct in_addr);
 889
 890           /* Lookup the vertex W's LSA. */
 891           w_lsa = ospf_lsa_lookup_by_id (area, OSPF_ROUTER_LSA, *r);
 892           if (w_lsa)
 893             {
 894               if (IS_DEBUG_OSPF_EVENT)
 895                 zlog_debug ("found Router LSA %s", inet_ntoa (w_lsa->data->id));
 896             }
 897         }
 898
 899       /* (b cont.) If the LSA does not exist, or its LS age is equal
 900          to MaxAge, or it does not have a link back to vertex V,
 901          examine the next link in V's LSA.[23] */
 902       if (w_lsa == NULL)
 903         {
 904           if (IS_DEBUG_OSPF_EVENT)
 905             zlog_debug ("No LSA found");
 906           continue;
 907         }
 908
 909       if (IS_LSA_MAXAGE (w_lsa))
 910         {
 911           if (IS_DEBUG_OSPF_EVENT)
 912             zlog_debug ("LSA is MaxAge");
 913           continue;
 914         }
 915
 916       if (ospf_lsa_has_link (w_lsa->data, v->lsa) < 0 )
 917         {
 918           if (IS_DEBUG_OSPF_EVENT)
 919             zlog_debug ("The LSA doesn't have a link back");
 920           continue;
 921         }
 922
 923       /* (c) If vertex W is already on the shortest-path tree, examine
 924          the next link in the LSA. */
 925       if (w_lsa->stat == LSA_SPF_IN_SPFTREE)
 926         {
 927           if (IS_DEBUG_OSPF_EVENT)
 928             zlog_debug ("The LSA is already in SPF");
 929           continue;
 930         }
 931
 932       /* (d) Calculate the link state cost D of the resulting path
 933          from the root to vertex W.  D is equal to the sum of the link
 934          state cost of the (already calculated) shortest path to
 935          vertex V and the advertised cost of the link between vertices
 936          V and W.  If D is: */
 937
 938       /* calculate link cost D. */
 939       if (v->lsa->type == OSPF_ROUTER_LSA)
 940         distance = v->distance + ntohs (l->m[0].metric);
 941       else /* v is not a Router-LSA */
 942         distance = v->distance;
 943
 944       /* Is there already vertex W in candidate list? */
 945       if (w_lsa->stat == LSA_SPF_NOT_EXPLORED)
 946         {
 947           /* prepare vertex W. */
 948           w = ospf_vertex_new (w_lsa);
 949
 950           /* Calculate nexthop to W. */
 951           if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
 952             pqueue_enqueue (w, candidate);
 953           else if (IS_DEBUG_OSPF_EVENT)
 954             zlog_debug ("Nexthop Calc failed");
 955         }
 956       else if (w_lsa->stat >= 0)
 957         {
 958           /* Get the vertex from candidates. */
 959           w = candidate->array[w_lsa->stat];
 960
 961           /* if D is greater than. */
 962           if (w->distance < distance)
 963             {
 964               continue;
 965             }
 966           /* equal to. */
 967           else if (w->distance == distance)
 968             {
 969               /* Found an equal-cost path to W.
 970                * Calculate nexthop of to W from V. */
 971               ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos);
 972             }
 973            /* less than. */
 974           else
 975             {
 976               /* Found a lower-cost path to W.
 977                * nexthop_calculation is conditional, if it finds
 978                * valid nexthop it will call spf_add_parents, which
 979                * will flush the old parents
 980                */
 981               if (ospf_nexthop_calculation (area, v, w, l, distance, lsa_pos))
 982                 /* Decrease the key of the node in the heap.
 983                  * trickle-sort it up towards root, just in case this
 984                  * node should now be the new root due the cost change.
 985                  * (next pqueu_{de,en}queue will fully re-heap the queue).
 986                  */
 987                 trickle_up (w_lsa->stat, candidate);
 988             }
 989         } /* end W is already on the candidate list */
 990     } /* end loop over the links in V's LSA */
 991 }
 992
 993 static void
 994 ospf_spf_dump (struct vertex *v, int i)
 995 {
 996   struct listnode *cnode;
 997   struct listnode *nnode;
 998   struct vertex_parent *parent;
 999
1000   if (v->type == OSPF_VERTEX_ROUTER)
1001     {
1002       if (IS_DEBUG_OSPF_EVENT)
1003         zlog_debug ("SPF Result: %d [R] %s", i, inet_ntoa (v->lsa->id));
1004     }
1005   else
1006     {
1007       struct network_lsa *lsa = (struct network_lsa *) v->lsa;
1008       if (IS_DEBUG_OSPF_EVENT)
1009         zlog_debug ("SPF Result: %d [N] %s/%d", i, inet_ntoa (v->lsa->id),
1010                    ip_masklen (lsa->mask));
1011     }
1012
1013   if (IS_DEBUG_OSPF_EVENT)
1014     for (ALL_LIST_ELEMENTS_RO (v->parents, nnode, parent))
1015       {
1016         zlog_debug (" nexthop %p %s %s",
1017                     (void *)parent->nexthop,
1018                     inet_ntoa (parent->nexthop->router),
1019                     parent->nexthop->oi ? IF_NAME(parent->nexthop->oi)
1020                                         : "NULL");
1021       }
1022
1023   i++;
1024
1025   for (ALL_LIST_ELEMENTS_RO (v->children, cnode, v))
1026     ospf_spf_dump (v, i);
1027 }
1028
1029 /* Second stage of SPF calculation. */
1030 static void
1031 ospf_spf_process_stubs (struct ospf_area *area, struct vertex *v,
1032                         struct route_table *rt,
1033                         int parent_is_root)
1034 {
1035   struct listnode *cnode, *cnnode;
1036   struct vertex *child;
1037
1038   if (IS_DEBUG_OSPF_EVENT)
1039     zlog_debug ("ospf_process_stub():processing stubs for area %s",
1040                inet_ntoa (area->area_id));
1041   if (v->type == OSPF_VERTEX_ROUTER)
1042     {
1043       u_char *p;
1044       u_char *lim;
1045       struct router_lsa_link *l;
1046       struct router_lsa *rlsa;
1047       int lsa_pos = 0;
1048
1049       if (IS_DEBUG_OSPF_EVENT)
1050         zlog_debug ("ospf_process_stubs():processing router LSA, id: %s",
1051                    inet_ntoa (v->lsa->id));
1052       rlsa = (struct router_lsa *) v->lsa;
1053
1054
1055       if (IS_DEBUG_OSPF_EVENT)
1056         zlog_debug ("ospf_process_stubs(): we have %d links to process",
1057                    ntohs (rlsa->links));
1058       p = ((u_char *) v->lsa) + OSPF_LSA_HEADER_SIZE + 4;
1059       lim = ((u_char *) v->lsa) + ntohs (v->lsa->length);
1060
1061       while (p < lim)
1062         {
1063           l = (struct router_lsa_link *) p;
1064
1065           p += (OSPF_ROUTER_LSA_LINK_SIZE +
1066                 (l->m[0].tos_count * OSPF_ROUTER_LSA_TOS_SIZE));
1067
1068           if (l->m[0].type == LSA_LINK_TYPE_STUB)
1069             ospf_intra_add_stub (rt, l, v, area, parent_is_root, lsa_pos);
1070           lsa_pos++;
1071         }
1072     }
1073
1074   ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v, 1, 1);
1075
1076   for (ALL_LIST_ELEMENTS (v->children, cnode, cnnode, child))
1077     {
1078       if (CHECK_FLAG (child->flags, OSPF_VERTEX_PROCESSED))
1079         continue;
1080
1081       /* the first level of routers connected to the root
1082        * should have 'parent_is_root' set, including those
1083        * connected via a network vertex.
1084        */
1085       if (area->spf == v)
1086         parent_is_root = 1;
1087       else if (v->type == OSPF_VERTEX_ROUTER)
1088         parent_is_root = 0;
1089
1090       ospf_spf_process_stubs (area, child, rt, parent_is_root);
1091
1092       SET_FLAG (child->flags, OSPF_VERTEX_PROCESSED);
1093     }
1094 }
1095
1096 void
1097 ospf_rtrs_free (struct route_table *rtrs)
1098 {
1099   struct route_node *rn;
1100   struct list *or_list;
1101   struct ospf_route *or;
1102   struct listnode *node, *nnode;
1103
1104   if (IS_DEBUG_OSPF_EVENT)
1105     zlog_debug ("Route: Router Routing Table free");
1106
1107   for (rn = route_top (rtrs); rn; rn = route_next (rn))
1108     if ((or_list = rn->info) != NULL)
1109       {
1110         for (ALL_LIST_ELEMENTS (or_list, node, nnode, or))
1111           ospf_route_free (or);
1112
1113         list_delete (or_list);
1114
1115         /* Unlock the node. */
1116         rn->info = NULL;
1117         route_unlock_node (rn);
1118       }
1119   route_table_finish (rtrs);
1120 }
1121
1122 #if 0
1123 static void
1124 ospf_rtrs_print (struct route_table *rtrs)
1125 {
1126   struct route_node *rn;
1127   struct list *or_list;
1128   struct listnode *ln;
1129   struct listnode *pnode;
1130   struct ospf_route *or;
1131   struct ospf_path *path;
1132   char buf1[BUFSIZ];
1133   char buf2[BUFSIZ];
1134
1135   if (IS_DEBUG_OSPF_EVENT)
1136     zlog_debug ("ospf_rtrs_print() start");
1137
1138   for (rn = route_top (rtrs); rn; rn = route_next (rn))
1139     if ((or_list = rn->info) != NULL)
1140       for (ALL_LIST_ELEMENTS_RO (or_list, ln, or))
1141         {
1142           switch (or->path_type)
1143             {
1144             case OSPF_PATH_INTRA_AREA:
1145               if (IS_DEBUG_OSPF_EVENT)
1146                 zlog_debug ("%s   [%d] area: %s",
1147                            inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1148                            or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1149                                                 buf2, BUFSIZ));
1150               break;
1151             case OSPF_PATH_INTER_AREA:
1152               if (IS_DEBUG_OSPF_EVENT)
1153                 zlog_debug ("%s IA [%d] area: %s",
1154                            inet_ntop (AF_INET, &or->id, buf1, BUFSIZ),
1155                            or->cost, inet_ntop (AF_INET, &or->u.std.area_id,
1156                                                 buf2, BUFSIZ));
1157               break;
1158             default:
1159               break;
1160             }
1161
1162           for (ALL_LIST_ELEMENTS_RO (or->paths, pnode, path))
1163             {
1164               if (path->nexthop.s_addr == 0)
1165                 {
1166                   if (IS_DEBUG_OSPF_EVENT)
1167                     zlog_debug ("   directly attached to %s\r\n",
1168                                 ifindex2ifname (path->ifindex));
1169                 }
1170               else
1171                 {
1172                   if (IS_DEBUG_OSPF_EVENT)
1173                     zlog_debug ("   via %s, %s\r\n",
1174                                 inet_ntoa (path->nexthop),
1175                                 ifindex2ifname (path->ifindex));
1176                 }
1177             }
1178         }
1179
1180   zlog_debug ("ospf_rtrs_print() end");
1181 }
1182 #endif
1183
1184 /* Calculating the shortest-path tree for an area. */
1185 static void
1186 ospf_spf_calculate (struct ospf_area *area, struct route_table *new_table,
1187                     struct route_table *new_rtrs)
1188 {
1189   struct pqueue *candidate;
1190   struct vertex *v;
1191
1192   if (IS_DEBUG_OSPF_EVENT)
1193     {
1194       zlog_debug ("ospf_spf_calculate: Start");
1195       zlog_debug ("ospf_spf_calculate: running Dijkstra for area %s",
1196                  inet_ntoa (area->area_id));
1197     }
1198
1199   /* Check router-lsa-self.  If self-router-lsa is not yet allocated,
1200      return this area's calculation. */
1201   if (!area->router_lsa_self)
1202     {
1203       if (IS_DEBUG_OSPF_EVENT)
1204         zlog_debug ("ospf_spf_calculate: "
1205                    "Skip area %s's calculation due to empty router_lsa_self",
1206                    inet_ntoa (area->area_id));
1207       return;
1208     }
1209
1210   /* RFC2328 16.1. (1). */
1211   /* Initialize the algorithm's data structures. */
1212
1213   /* This function scans all the LSA database and set the stat field to
1214    * LSA_SPF_NOT_EXPLORED. */
1215   ospf_lsdb_clean_stat (area->lsdb);
1216   /* Create a new heap for the candidates. */
1217   candidate = pqueue_create();
1218   candidate->cmp = cmp;
1219   candidate->update = update_stat;
1220
1221   /* Initialize the shortest-path tree to only the root (which is the
1222      router doing the calculation). */
1223   ospf_spf_init (area);
1224   v = area->spf;
1225   /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of the
1226    * spanning tree. */
1227   *(v->stat) = LSA_SPF_IN_SPFTREE;
1228
1229   /* Set Area A's TransitCapability to FALSE. */
1230   area->transit = OSPF_TRANSIT_FALSE;
1231   area->shortcut_capability = 1;
1232
1233   for (;;)
1234     {
1235       /* RFC2328 16.1. (2). */
1236       ospf_spf_next (v, area, candidate);
1237
1238       /* RFC2328 16.1. (3). */
1239       /* If at this step the candidate list is empty, the shortest-
1240          path tree (of transit vertices) has been completely built and
1241          this stage of the procedure terminates. */
1242       if (candidate->size == 0)
1243         break;
1244
1245       /* Otherwise, choose the vertex belonging to the candidate list
1246          that is closest to the root, and add it to the shortest-path
1247          tree (removing it from the candidate list in the
1248          process). */
1249       /* Extract from the candidates the node with the lower key. */
1250       v = (struct vertex *) pqueue_dequeue (candidate);
1251       /* Update stat field in vertex. */
1252       *(v->stat) = LSA_SPF_IN_SPFTREE;
1253
1254       ospf_vertex_add_parent (v);
1255
1256       /* RFC2328 16.1. (4). */
1257       if (v->type == OSPF_VERTEX_ROUTER)
1258         ospf_intra_add_router (new_rtrs, v, area);
1259       else
1260         ospf_intra_add_transit (new_table, v, area);
1261
1262       /* RFC2328 16.1. (5). */
1263       /* Iterate the algorithm by returning to Step 2. */
1264
1265     } /* end loop until no more candidate vertices */
1266
1267   if (IS_DEBUG_OSPF_EVENT)
1268     {
1269       ospf_spf_dump (area->spf, 0);
1270       ospf_route_table_dump (new_table);
1271     }
1272
1273   /* Second stage of SPF calculation procedure's  */
1274   ospf_spf_process_stubs (area, area->spf, new_table, 0);
1275
1276   /* Free candidate queue. */
1277   pqueue_delete (candidate);
1278
1279   ospf_vertex_dump (__func__, area->spf, 0, 1);
1280   /* Free nexthop information, canonical versions of which are attached
1281    * the first level of router vertices attached to the root vertex, see
1282    * ospf_nexthop_calculation.
1283    */
1284   ospf_canonical_nexthops_free (area->spf);
1285
1286   /* Increment SPF Calculation Counter. */
1287   area->spf_calculation++;
1288
1289   quagga_gettime (QUAGGA_CLK_MONOTONIC, &area->ospf->ts_spf);
1290   area->ts_spf = area->ospf->ts_spf;
1291
1292   if (IS_DEBUG_OSPF_EVENT)
1293     zlog_debug ("ospf_spf_calculate: Stop. %zd vertices",
1294                 mtype_stats_alloc(MTYPE_OSPF_VERTEX));
1295
1296   /* Free SPF vertices, but not the list. List has ospf_vertex_free
1297    * as deconstructor.
1298    */
1299   list_delete_all_node (&vertex_list);
1300 }
1301
1302 /* Timer for SPF calculation. */
1303 static int
1304 ospf_spf_calculate_timer (struct thread *thread)
1305 {
1306   struct ospf *ospf = THREAD_ARG (thread);
1307   struct route_table *new_table, *new_rtrs;
1308   struct ospf_area *area;
1309   struct listnode *node, *nnode;
1310   struct timeval start_time, stop_time, spf_start_time;
1311   int areas_processed = 0;
1312   unsigned long ia_time, prune_time, rt_time;
1313   unsigned long abr_time, total_spf_time, spf_time;
1314   char rbuf[32];                /* reason_buf */
1315
1316   if (IS_DEBUG_OSPF_EVENT)
1317     zlog_debug ("SPF: Timer (SPF calculation expire)");
1318
1319   ospf->t_spf_calc = NULL;
1320
1321   quagga_gettime (QUAGGA_CLK_MONOTONIC, &spf_start_time);
1322   /* Allocate new table tree. */
1323   new_table = route_table_init ();
1324   new_rtrs = route_table_init ();
1325
1326   ospf_vl_unapprove (ospf);
1327
1328   /* Calculate SPF for each area. */
1329   for (ALL_LIST_ELEMENTS (ospf->areas, node, nnode, area))
1330     {
1331       /* Do backbone last, so as to first discover intra-area paths
1332        * for any back-bone virtual-links
1333        */
1334       if (ospf->backbone && ospf->backbone == area)
1335         continue;
1336
1337       ospf_spf_calculate (area, new_table, new_rtrs);
1338       areas_processed++;
1339     }
1340
1341   /* SPF for backbone, if required */
1342   if (ospf->backbone)
1343     {
1344       ospf_spf_calculate (ospf->backbone, new_table, new_rtrs);
1345       areas_processed++;
1346     }
1347
1348   quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
1349   spf_time = timeval_elapsed (stop_time, spf_start_time);
1350
1351   ospf_vl_shut_unapproved (ospf);
1352
1353   start_time = stop_time;       /* saving a call */
1354
1355   ospf_ia_routing (ospf, new_table, new_rtrs);
1356
1357   quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
1358   ia_time = timeval_elapsed (stop_time, start_time);
1359
1360   quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
1361   ospf_prune_unreachable_networks (new_table);
1362   ospf_prune_unreachable_routers (new_rtrs);
1363
1364   quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
1365   prune_time = timeval_elapsed (stop_time, start_time);
1366   /* AS-external-LSA calculation should not be performed here. */
1367
1368   /* If new Router Route is installed,
1369      then schedule re-calculate External routes. */
1370   if (1)
1371     ospf_ase_calculate_schedule (ospf);
1372
1373   ospf_ase_calculate_timer_add (ospf);
1374
1375   quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
1376
1377   /* Update routing table. */
1378   ospf_route_install (ospf, new_table);
1379
1380   quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
1381   rt_time = timeval_elapsed (stop_time, start_time);
1382   /* Update ABR/ASBR routing table */
1383   if (ospf->old_rtrs)
1384     {
1385       /* old_rtrs's node holds linked list of ospf_route. --kunihiro. */
1386       /* ospf_route_delete (ospf->old_rtrs); */
1387       ospf_rtrs_free (ospf->old_rtrs);
1388     }
1389
1390   ospf->old_rtrs = ospf->new_rtrs;
1391   ospf->new_rtrs = new_rtrs;
1392
1393   quagga_gettime (QUAGGA_CLK_MONOTONIC, &start_time);
1394   if (IS_OSPF_ABR (ospf))
1395     ospf_abr_task (ospf);
1396
1397   quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
1398   abr_time = timeval_elapsed (stop_time, start_time);
1399
1400   quagga_gettime (QUAGGA_CLK_MONOTONIC, &stop_time);
1401   total_spf_time = timeval_elapsed (stop_time, spf_start_time);
1402   ospf->ts_spf_duration.tv_sec = total_spf_time/1000000;
1403   ospf->ts_spf_duration.tv_usec = total_spf_time % 1000000;
1404
1405   ospf_get_spf_reason_str (rbuf);
1406
1407   if (IS_DEBUG_OSPF_EVENT)
1408     {
1409       zlog_info ("SPF Processing Time(usecs): %ld", total_spf_time);
1410       zlog_info ("\t    SPF Time: %ld", spf_time);
1411       zlog_info ("\t   InterArea: %ld", ia_time);
1412       zlog_info ("\t       Prune: %ld", prune_time);
1413       zlog_info ("\tRouteInstall: %ld", rt_time);
1414       if (IS_OSPF_ABR (ospf))
1415         zlog_info ("\t         ABR: %ld (%d areas)",
1416                    abr_time, areas_processed);
1417       zlog_info ("Reason(s) for SPF: %s", rbuf);
1418     }
1419
1420   ospf_clear_spf_reason_flags ();
1421
1422   return 0;
1423 }
1424
1425 /* Add schedule for SPF calculation.  To avoid frequenst SPF calc, we
1426    set timer for SPF calc. */
1427 void
1428 ospf_spf_calculate_schedule (struct ospf *ospf, ospf_spf_reason_t reason)
1429 {
1430   unsigned long delay, elapsed, ht;
1431   struct timeval result;
1432
1433   if (IS_DEBUG_OSPF_EVENT)
1434     zlog_debug ("SPF: calculation timer scheduled");
1435
1436   /* OSPF instance does not exist. */
1437   if (ospf == NULL)
1438     return;
1439
1440   ospf_spf_set_reason (reason);
1441
1442   /* SPF calculation timer is already scheduled. */
1443   if (ospf->t_spf_calc)
1444     {
1445       if (IS_DEBUG_OSPF_EVENT)
1446         zlog_debug ("SPF: calculation timer is already scheduled: %p",
1447                     (void *)ospf->t_spf_calc);
1448       return;
1449     }
1450
1451   /* XXX Monotic timers: we only care about relative time here. */
1452   result = tv_sub (recent_relative_time (), ospf->ts_spf);
1453
1454   elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
1455   ht = ospf->spf_holdtime * ospf->spf_hold_multiplier;
1456
1457   if (ht > ospf->spf_max_holdtime)
1458     ht = ospf->spf_max_holdtime;
1459
1460   /* Get SPF calculation delay time. */
1461   if (elapsed < ht)
1462     {
1463       /* Got an event within the hold time of last SPF. We need to
1464        * increase the hold_multiplier, if it's not already at/past
1465        * maximum value, and wasn't already increased..
1466        */
1467       if (ht < ospf->spf_max_holdtime)
1468         ospf->spf_hold_multiplier++;
1469
1470       /* always honour the SPF initial delay */
1471       if ( (ht - elapsed) < ospf->spf_delay)
1472         delay = ospf->spf_delay;
1473       else
1474         delay = ht - elapsed;
1475     }
1476   else
1477     {
1478       /* Event is past required hold-time of last SPF */
1479       delay = ospf->spf_delay;
1480       ospf->spf_hold_multiplier = 1;
1481     }
1482
1483   if (IS_DEBUG_OSPF_EVENT)
1484     zlog_debug ("SPF: calculation timer delay = %ld", delay);
1485
1486   zlog_info ("SPF: Scheduled in %ld msec", delay);
1487
1488   ospf->t_spf_calc =
1489     thread_add_timer_msec (master, ospf_spf_calculate_timer, ospf, delay);
1490 }