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