ospf6d/ospf6_spf.c

   1 /*
   2  * Copyright (C) 2003 Yasuhiro Ohara
   3  *
   4  * This file is part of GNU Zebra.
   5  *
   6  * GNU Zebra is free software; you can redistribute it and/or modify it
   7  * under the terms of the GNU General Public License as published by the
   8  * Free Software Foundation; either version 2, or (at your option) any
   9  * later version.
  10  *
  11  * GNU Zebra is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with GNU Zebra; see the file COPYING.  If not, write to the
  18  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  19  * Boston, MA 02111-1307, USA.
  20  */
  21
  22 /* Shortest Path First calculation for OSPFv3 */
  23
  24 #include <zebra.h>
  25
  26 #include "log.h"
  27 #include "memory.h"
  28 #include "command.h"
  29 #include "vty.h"
  30 #include "prefix.h"
  31 #include "pqueue.h"
  32 #include "linklist.h"
  33 #include "thread.h"
  34
  35 #include "ospf6_lsa.h"
  36 #include "ospf6_lsdb.h"
  37 #include "ospf6_route.h"
  38 #include "ospf6_area.h"
  39 #include "ospf6_spf.h"
  40 #include "ospf6_intra.h"
  41 #include "ospf6_interface.h"
  42 #include "ospf6d.h"
  43 #include "ospf6_abr.h"
  44
  45 unsigned char conf_debug_ospf6_spf = 0;
  46
  47 static int
  48 ospf6_vertex_cmp (void *a, void *b)
  49 {
  50   struct ospf6_vertex *va = (struct ospf6_vertex *) a;
  51   struct ospf6_vertex *vb = (struct ospf6_vertex *) b;
  52
  53   /* ascending order */
  54   if (va->cost != vb->cost)
  55     return (va->cost - vb->cost);
  56   return (va->hops - vb->hops);
  57 }
  58
  59 static int
  60 ospf6_vertex_id_cmp (void *a, void *b)
  61 {
  62   struct ospf6_vertex *va = (struct ospf6_vertex *) a;
  63   struct ospf6_vertex *vb = (struct ospf6_vertex *) b;
  64   int ret = 0;
  65
  66   ret = ntohl (ospf6_linkstate_prefix_adv_router (&va->vertex_id)) -
  67         ntohl (ospf6_linkstate_prefix_adv_router (&vb->vertex_id));
  68   if (ret)
  69     return ret;
  70
  71   ret = ntohl (ospf6_linkstate_prefix_id (&va->vertex_id)) -
  72         ntohl (ospf6_linkstate_prefix_id (&vb->vertex_id));
  73   return ret;
  74 }
  75
  76 static struct ospf6_vertex *
  77 ospf6_vertex_create (struct ospf6_lsa *lsa)
  78 {
  79   struct ospf6_vertex *v;
  80   int i;
  81
  82   v = (struct ospf6_vertex *)
  83     XMALLOC (MTYPE_OSPF6_VERTEX, sizeof (struct ospf6_vertex));
  84
  85   /* type */
  86   if (ntohs (lsa->header->type) == OSPF6_LSTYPE_ROUTER)
  87     v->type = OSPF6_VERTEX_TYPE_ROUTER;
  88   else if (ntohs (lsa->header->type) == OSPF6_LSTYPE_NETWORK)
  89     v->type = OSPF6_VERTEX_TYPE_NETWORK;
  90   else
  91     assert (0);
  92
  93   /* vertex_id */
  94   ospf6_linkstate_prefix (lsa->header->adv_router, lsa->header->id,
  95                           &v->vertex_id);
  96
  97   /* name */
  98   ospf6_linkstate_prefix2str (&v->vertex_id, v->name, sizeof (v->name));
  99
 100   /* Associated LSA */
 101   v->lsa = lsa;
 102
 103   /* capability bits + options */
 104   v->capability = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header));
 105   v->options[0] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 1);
 106   v->options[1] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 2);
 107   v->options[2] = *(u_char *)(OSPF6_LSA_HEADER_END (lsa->header) + 3);
 108
 109   for (i = 0; i < OSPF6_MULTI_PATH_LIMIT; i++)
 110     ospf6_nexthop_clear (&v->nexthop[i]);
 111
 112   v->parent = NULL;
 113   v->child_list = list_new ();
 114   v->child_list->cmp = ospf6_vertex_id_cmp;
 115
 116   return v;
 117 }
 118
 119 static void
 120 ospf6_vertex_delete (struct ospf6_vertex *v)
 121 {
 122   list_delete (v->child_list);
 123   XFREE (MTYPE_OSPF6_VERTEX, v);
 124 }
 125
 126 static struct ospf6_lsa *
 127 ospf6_lsdesc_lsa (caddr_t lsdesc, struct ospf6_vertex *v)
 128 {
 129   struct ospf6_lsa *lsa;
 130   u_int16_t type = 0;
 131   u_int32_t id = 0, adv_router = 0;
 132
 133   if (VERTEX_IS_TYPE (NETWORK, v))
 134     {
 135       type = htons (OSPF6_LSTYPE_ROUTER);
 136       id = htonl (0);
 137       adv_router = NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc);
 138     }
 139   else
 140     {
 141       if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc))
 142         {
 143           type = htons (OSPF6_LSTYPE_ROUTER);
 144           id = htonl (0);
 145           adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc);
 146         }
 147       else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, lsdesc))
 148         {
 149           type = htons (OSPF6_LSTYPE_NETWORK);
 150           id = htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc));
 151           adv_router = ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc);
 152         }
 153     }
 154
 155   lsa = ospf6_lsdb_lookup (type, id, adv_router, v->area->lsdb);
 156
 157   if (IS_OSPF6_DEBUG_SPF (PROCESS))
 158     {
 159       char ibuf[16], abuf[16];
 160       inet_ntop (AF_INET, &id, ibuf, sizeof (ibuf));
 161       inet_ntop (AF_INET, &adv_router, abuf, sizeof (abuf));
 162       if (lsa)
 163         zlog_debug ("  Link to: %s", lsa->name);
 164       else
 165         zlog_debug ("  Link to: [%s Id:%s Adv:%s] No LSA",
 166                     ospf6_lstype_name (type), ibuf, abuf);
 167     }
 168
 169   return lsa;
 170 }
 171
 172 static char *
 173 ospf6_lsdesc_backlink (struct ospf6_lsa *lsa,
 174                        caddr_t lsdesc, struct ospf6_vertex *v)
 175 {
 176   caddr_t backlink, found = NULL;
 177   int size;
 178
 179   size = (OSPF6_LSA_IS_TYPE (ROUTER, lsa) ?
 180           sizeof (struct ospf6_router_lsdesc) :
 181           sizeof (struct ospf6_network_lsdesc));
 182   for (backlink = OSPF6_LSA_HEADER_END (lsa->header) + 4;
 183        backlink + size <= OSPF6_LSA_END (lsa->header); backlink += size)
 184     {
 185       assert (! (OSPF6_LSA_IS_TYPE (NETWORK, lsa) &&
 186                  VERTEX_IS_TYPE (NETWORK, v)));
 187
 188       if (OSPF6_LSA_IS_TYPE (NETWORK, lsa) &&
 189           NETWORK_LSDESC_GET_NBR_ROUTERID (backlink)
 190             == v->lsa->header->adv_router)
 191         found = backlink;
 192       else if (VERTEX_IS_TYPE (NETWORK, v) &&
 193           ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK, backlink) &&
 194           ROUTER_LSDESC_GET_NBR_ROUTERID (backlink)
 195             == v->lsa->header->adv_router &&
 196           ROUTER_LSDESC_GET_NBR_IFID (backlink)
 197             == ntohl (v->lsa->header->id))
 198         found = backlink;
 199       else
 200         {
 201           if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, backlink) ||
 202               ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT, lsdesc))
 203             continue;
 204           if (ROUTER_LSDESC_GET_NBR_IFID (backlink) !=
 205               ROUTER_LSDESC_GET_IFID (lsdesc) ||
 206               ROUTER_LSDESC_GET_NBR_IFID (lsdesc) !=
 207               ROUTER_LSDESC_GET_IFID (backlink))
 208             continue;
 209           if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink) !=
 210               v->lsa->header->adv_router ||
 211               ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc) !=
 212               lsa->header->adv_router)
 213             continue;
 214           found = backlink;
 215         }
 216     }
 217
 218   if (IS_OSPF6_DEBUG_SPF (PROCESS))
 219     zlog_debug ("  Backlink %s", (found ? "OK" : "FAIL"));
 220
 221   return found;
 222 }
 223
 224 static void
 225 ospf6_nexthop_calc (struct ospf6_vertex *w, struct ospf6_vertex *v,
 226                     caddr_t lsdesc)
 227 {
 228   int i;
 229   ifindex_t ifindex;
 230   struct ospf6_interface *oi;
 231   u_int16_t type;
 232   u_int32_t adv_router;
 233   struct ospf6_lsa *lsa;
 234   struct ospf6_link_lsa *link_lsa;
 235   char buf[64];
 236
 237   assert (VERTEX_IS_TYPE (ROUTER, w));
 238   ifindex = (VERTEX_IS_TYPE (NETWORK, v) ? v->nexthop[0].ifindex :
 239              /* v is the local router & the interface_id is a local ifindex */
 240              (ifindex_t) ROUTER_LSDESC_GET_IFID (lsdesc));
 241   assert (ifindex >= 0);
 242
 243   oi = ospf6_interface_lookup_by_ifindex (ifindex);
 244   if (oi == NULL)
 245     {
 246       if (IS_OSPF6_DEBUG_SPF (PROCESS))
 247         zlog_debug ("Can't find interface in SPF: ifindex %d", ifindex);
 248       return;
 249     }
 250
 251   type = htons (OSPF6_LSTYPE_LINK);
 252   adv_router = (VERTEX_IS_TYPE (NETWORK, v) ?
 253                 NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc) :
 254                 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc));
 255
 256   i = 0;
 257   for (lsa = ospf6_lsdb_type_router_head (type, adv_router, oi->lsdb); lsa;
 258        lsa = ospf6_lsdb_type_router_next (type, adv_router, lsa))
 259     {
 260       if (VERTEX_IS_TYPE (ROUTER, v) &&
 261           htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc)) != lsa->header->id)
 262         continue;
 263
 264       link_lsa = (struct ospf6_link_lsa *) OSPF6_LSA_HEADER_END (lsa->header);
 265       if (IS_OSPF6_DEBUG_SPF (PROCESS))
 266         {
 267           inet_ntop (AF_INET6, &link_lsa->linklocal_addr, buf, sizeof (buf));
 268           zlog_debug ("  nexthop %s from %s", buf, lsa->name);
 269         }
 270
 271       if (i < OSPF6_MULTI_PATH_LIMIT)
 272         {
 273           memcpy (&w->nexthop[i].address, &link_lsa->linklocal_addr,
 274                   sizeof (struct in6_addr));
 275           w->nexthop[i].ifindex = ifindex;
 276           i++;
 277         }
 278     }
 279
 280   if (i == 0 && IS_OSPF6_DEBUG_SPF (PROCESS))
 281     zlog_debug ("No nexthop for %s found", w->name);
 282 }
 283
 284 static int
 285 ospf6_spf_install (struct ospf6_vertex *v,
 286                    struct ospf6_route_table *result_table)
 287 {
 288   struct ospf6_route *route;
 289   int i, j;
 290   struct ospf6_vertex *prev;
 291
 292   if (IS_OSPF6_DEBUG_SPF (PROCESS))
 293     zlog_debug ("SPF install %s hops %d cost %d",
 294                 v->name, v->hops, v->cost);
 295
 296   route = ospf6_route_lookup (&v->vertex_id, result_table);
 297   if (route && route->path.cost < v->cost)
 298     {
 299       if (IS_OSPF6_DEBUG_SPF (PROCESS))
 300         zlog_debug ("  already installed with lower cost (%d), ignore",
 301                     route->path.cost);
 302       ospf6_vertex_delete (v);
 303       return -1;
 304     }
 305   else if (route && route->path.cost == v->cost)
 306     {
 307       if (IS_OSPF6_DEBUG_SPF (PROCESS))
 308         zlog_debug ("  another path found, merge");
 309
 310       for (i = 0; i < OSPF6_MULTI_PATH_LIMIT &&
 311            ospf6_nexthop_is_set (&v->nexthop[i]); i++)
 312         {
 313           for (j = 0; j < OSPF6_MULTI_PATH_LIMIT; j++)
 314             {
 315               if (ospf6_nexthop_is_set (&route->nexthop[j]))
 316                 {
 317                   if (ospf6_nexthop_is_same (&route->nexthop[j],
 318                                              &v->nexthop[i]))
 319                     break;
 320                   else
 321                     continue;
 322                 }
 323               ospf6_nexthop_copy (&route->nexthop[j], &v->nexthop[i]);
 324               break;
 325             }
 326         }
 327
 328       prev = (struct ospf6_vertex *) route->route_option;
 329       assert (prev->hops <= v->hops);
 330       ospf6_vertex_delete (v);
 331
 332       return -1;
 333     }
 334
 335   /* There should be no case where candidate being installed (variable
 336      "v") is closer than the one in the SPF tree (variable "route").
 337      In the case something has gone wrong with the behavior of
 338      Priority-Queue. */
 339
 340   /* the case where the route exists already is handled and returned
 341      up to here. */
 342   assert (route == NULL);
 343
 344   route = ospf6_route_create ();
 345   memcpy (&route->prefix, &v->vertex_id, sizeof (struct prefix));
 346   route->type = OSPF6_DEST_TYPE_LINKSTATE;
 347   route->path.type = OSPF6_PATH_TYPE_INTRA;
 348   route->path.origin.type = v->lsa->header->type;
 349   route->path.origin.id = v->lsa->header->id;
 350   route->path.origin.adv_router = v->lsa->header->adv_router;
 351   route->path.metric_type = 1;
 352   route->path.cost = v->cost;
 353   route->path.cost_e2 = v->hops;
 354   route->path.router_bits = v->capability;
 355   route->path.options[0] = v->options[0];
 356   route->path.options[1] = v->options[1];
 357   route->path.options[2] = v->options[2];
 358
 359   for (i = 0; i < OSPF6_MULTI_PATH_LIMIT &&
 360        ospf6_nexthop_is_set (&v->nexthop[i]); i++)
 361     ospf6_nexthop_copy (&route->nexthop[i], &v->nexthop[i]);
 362
 363   if (v->parent)
 364     listnode_add_sort (v->parent->child_list, v);
 365   route->route_option = v;
 366
 367   ospf6_route_add (route, result_table);
 368   return 0;
 369 }
 370
 371 void
 372 ospf6_spf_table_finish (struct ospf6_route_table *result_table)
 373 {
 374   struct ospf6_route *route, *nroute;
 375   struct ospf6_vertex *v;
 376   for (route = ospf6_route_head (result_table); route;
 377        route = nroute)
 378     {
 379       nroute = ospf6_route_next (route);
 380       v = (struct ospf6_vertex *) route->route_option;
 381       ospf6_vertex_delete (v);
 382       ospf6_route_remove (route, result_table);
 383     }
 384 }
 385
 386 static const char *ospf6_spf_reason_str[] =
 387   {
 388     "R+",
 389     "R-",
 390     "N+",
 391     "N-",
 392     "L+",
 393     "L-",
 394     "R*",
 395     "N*",
 396   };
 397
 398 void ospf6_spf_reason_string (unsigned int reason, char *buf, int size)
 399 {
 400   size_t bit;
 401   int len = 0;
 402
 403   if (!buf)
 404     return;
 405
 406   for (bit = 0; bit < array_size(ospf6_spf_reason_str); bit++)
 407     {
 408       if ((reason & (1 << bit)) && (len < size))
 409         {
 410           len += snprintf((buf + len), (size - len), "%s%s",
 411                           (len > 0) ? ", " : "", ospf6_spf_reason_str[bit]);
 412         }
 413     }
 414 }
 415
 416 /* RFC2328 16.1.  Calculating the shortest-path tree for an area */
 417 /* RFC2740 3.8.1.  Calculating the shortest path tree for an area */
 418 void
 419 ospf6_spf_calculation (u_int32_t router_id,
 420                        struct ospf6_route_table *result_table,
 421                        struct ospf6_area *oa)
 422 {
 423   struct pqueue *candidate_list;
 424   struct ospf6_vertex *root, *v, *w;
 425   int i;
 426   int size;
 427   caddr_t lsdesc;
 428   struct ospf6_lsa *lsa;
 429
 430   ospf6_spf_table_finish (result_table);
 431
 432   /* Install the calculating router itself as the root of the SPF tree */
 433   /* construct root vertex */
 434   lsa = ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER), htonl (0),
 435                            router_id, oa->lsdb);
 436   if (lsa == NULL)
 437     return;
 438
 439   /* initialize */
 440   candidate_list = pqueue_create ();
 441   candidate_list->cmp = ospf6_vertex_cmp;
 442
 443   root = ospf6_vertex_create (lsa);
 444   root->area = oa;
 445   root->cost = 0;
 446   root->hops = 0;
 447   root->nexthop[0].ifindex = 0; /* loopbak I/F is better ... */
 448   inet_pton (AF_INET6, "::1", &root->nexthop[0].address);
 449
 450   /* Actually insert root to the candidate-list as the only candidate */
 451   pqueue_enqueue (root, candidate_list);
 452
 453   /* Iterate until candidate-list becomes empty */
 454   while (candidate_list->size)
 455     {
 456       /* get closest candidate from priority queue */
 457       v = pqueue_dequeue (candidate_list);
 458
 459       /* installing may result in merging or rejecting of the vertex */
 460       if (ospf6_spf_install (v, result_table) < 0)
 461         continue;
 462
 463       /* Skip overloaded routers */
 464       if ((OSPF6_LSA_IS_TYPE (ROUTER, v->lsa) &&
 465            ospf6_router_is_stub_router (v->lsa)))
 466         continue;
 467
 468       /* For each LS description in the just-added vertex V's LSA */
 469       size = (VERTEX_IS_TYPE (ROUTER, v) ?
 470               sizeof (struct ospf6_router_lsdesc) :
 471               sizeof (struct ospf6_network_lsdesc));
 472       for (lsdesc = OSPF6_LSA_HEADER_END (v->lsa->header) + 4;
 473            lsdesc + size <= OSPF6_LSA_END (v->lsa->header); lsdesc += size)
 474         {
 475           lsa = ospf6_lsdesc_lsa (lsdesc, v);
 476           if (lsa == NULL)
 477             continue;
 478
 479           if (! ospf6_lsdesc_backlink (lsa, lsdesc, v))
 480             continue;
 481
 482           w = ospf6_vertex_create (lsa);
 483           w->area = oa;
 484           w->parent = v;
 485           if (VERTEX_IS_TYPE (ROUTER, v))
 486             {
 487               w->cost = v->cost + ROUTER_LSDESC_GET_METRIC (lsdesc);
 488               w->hops = v->hops + (VERTEX_IS_TYPE (NETWORK, w) ? 0 : 1);
 489             }
 490           else /* NETWORK */
 491             {
 492               w->cost = v->cost;
 493               w->hops = v->hops + 1;
 494             }
 495
 496           /* nexthop calculation */
 497           if (w->hops == 0)
 498             w->nexthop[0].ifindex = ROUTER_LSDESC_GET_IFID (lsdesc);
 499           else if (w->hops == 1 && v->hops == 0)
 500             ospf6_nexthop_calc (w, v, lsdesc);
 501           else
 502             {
 503               for (i = 0; i < OSPF6_MULTI_PATH_LIMIT &&
 504                    ospf6_nexthop_is_set (&v->nexthop[i]); i++)
 505                 ospf6_nexthop_copy (&w->nexthop[i], &v->nexthop[i]);
 506             }
 507
 508           /* add new candidate to the candidate_list */
 509           if (IS_OSPF6_DEBUG_SPF (PROCESS))
 510             zlog_debug ("  New candidate: %s hops %d cost %d",
 511                         w->name, w->hops, w->cost);
 512           pqueue_enqueue (w, candidate_list);
 513         }
 514     }
 515
 516   pqueue_delete (candidate_list);
 517
 518   oa->spf_calculation++;
 519 }
 520
 521 static void
 522 ospf6_spf_log_database (struct ospf6_area *oa)
 523 {
 524   char *p, *end, buffer[256];
 525   struct listnode *node;
 526   struct ospf6_interface *oi;
 527
 528   p = buffer;
 529   end = buffer + sizeof (buffer);
 530
 531   snprintf (p, end - p, "SPF on DB (#LSAs):");
 532   p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
 533   snprintf (p, end - p, " Area %s: %d", oa->name, oa->lsdb->count);
 534   p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
 535
 536   for (ALL_LIST_ELEMENTS_RO (oa->if_list, node, oi))
 537     {
 538       snprintf (p, end - p, " I/F %s: %d",
 539                 oi->interface->name, oi->lsdb->count);
 540       p = (buffer + strlen (buffer) < end ? buffer + strlen (buffer) : end);
 541     }
 542
 543   zlog_debug ("%s", buffer);
 544 }
 545
 546 static int
 547 ospf6_spf_calculation_thread (struct thread *t)
 548 {
 549   struct ospf6_area *oa;
 550   struct ospf6 *ospf6;
 551   struct timeval start, end, runtime;
 552   struct listnode *node;
 553   struct ospf6_route *route;
 554   int areas_processed = 0;
 555   char rbuf[32];
 556
 557   ospf6 = (struct ospf6 *)THREAD_ARG (t);
 558   ospf6->t_spf_calc = NULL;
 559
 560   /* execute SPF calculation */
 561   quagga_gettime (QUAGGA_CLK_MONOTONIC, &start);
 562
 563   for (ALL_LIST_ELEMENTS_RO(ospf6->area_list, node, oa))
 564     {
 565
 566       if (oa == ospf6->backbone)
 567         continue;
 568
 569       if (IS_OSPF6_DEBUG_SPF (PROCESS))
 570         zlog_debug ("SPF calculation for Area %s", oa->name);
 571       if (IS_OSPF6_DEBUG_SPF (DATABASE))
 572         ospf6_spf_log_database (oa);
 573
 574       ospf6_spf_calculation (ospf6->router_id, oa->spf_table, oa);
 575       ospf6_intra_route_calculation (oa);
 576       ospf6_intra_brouter_calculation (oa);
 577
 578       areas_processed++;
 579     }
 580
 581   if (ospf6->backbone)
 582     {
 583       if (IS_OSPF6_DEBUG_SPF (PROCESS))
 584         zlog_debug ("SPF calculation for Backbone area %s",
 585                     ospf6->backbone->name);
 586       if (IS_OSPF6_DEBUG_SPF (DATABASE))
 587         ospf6_spf_log_database(ospf6->backbone);
 588
 589       ospf6_spf_calculation(ospf6->router_id, ospf6->backbone->spf_table,
 590                             ospf6->backbone);
 591       ospf6_intra_route_calculation(ospf6->backbone);
 592       ospf6_intra_brouter_calculation(ospf6->backbone);
 593       areas_processed++;
 594     }
 595
 596   /* Redo summaries if required */
 597   for (route = ospf6_route_head (ospf6->route_table); route;
 598        route = ospf6_route_next (route))
 599     ospf6_abr_originate_summary(route);
 600
 601   quagga_gettime (QUAGGA_CLK_MONOTONIC, &end);
 602   timersub (&end, &start, &runtime);
 603
 604   ospf6->ts_spf_duration = runtime;
 605
 606   ospf6_spf_reason_string(ospf6->spf_reason, rbuf, sizeof(rbuf));
 607
 608   if (IS_OSPF6_DEBUG_SPF (PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
 609     zlog_debug ("SPF runtime: %lld sec %lld usec",
 610                 (long long)runtime.tv_sec, (long long)runtime.tv_usec);
 611
 612   zlog_info("SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
 613             "Reason: %s\n", areas_processed,
 614             (long long)runtime.tv_sec, (long long)runtime.tv_usec,
 615             rbuf);
 616   ospf6->last_spf_reason = ospf6->spf_reason;
 617   ospf6_reset_spf_reason(ospf6);
 618   return 0;
 619 }
 620
 621 /* Add schedule for SPF calculation.  To avoid frequenst SPF calc, we
 622    set timer for SPF calc. */
 623 void
 624 ospf6_spf_schedule (struct ospf6 *ospf6, unsigned int reason)
 625 {
 626   unsigned long delay, elapsed, ht;
 627   struct timeval now, result;
 628
 629   ospf6_set_spf_reason(ospf6, reason);
 630
 631   if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
 632     {
 633       char rbuf[32];
 634       ospf6_spf_reason_string(reason, rbuf, sizeof(rbuf));
 635       zlog_debug ("SPF: calculation timer scheduled (reason %s)", rbuf);
 636     }
 637
 638   /* OSPF instance does not exist. */
 639   if (ospf6 == NULL)
 640     return;
 641
 642   /* SPF calculation timer is already scheduled. */
 643   if (ospf6->t_spf_calc)
 644     {
 645       if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
 646         zlog_debug ("SPF: calculation timer is already scheduled: %p",
 647                     (void *)ospf6->t_spf_calc);
 648       return;
 649     }
 650
 651   /* XXX Monotic timers: we only care about relative time here. */
 652   now = recent_relative_time ();
 653   timersub (&now, &ospf6->ts_spf, &result);
 654
 655   elapsed = (result.tv_sec * 1000) + (result.tv_usec / 1000);
 656   ht = ospf6->spf_holdtime * ospf6->spf_hold_multiplier;
 657
 658   if (ht > ospf6->spf_max_holdtime)
 659     ht = ospf6->spf_max_holdtime;
 660
 661   /* Get SPF calculation delay time. */
 662   if (elapsed < ht)
 663     {
 664       /* Got an event within the hold time of last SPF. We need to
 665        * increase the hold_multiplier, if it's not already at/past
 666        * maximum value, and wasn't already increased..
 667        */
 668       if (ht < ospf6->spf_max_holdtime)
 669         ospf6->spf_hold_multiplier++;
 670
 671       /* always honour the SPF initial delay */
 672       if ( (ht - elapsed) < ospf6->spf_delay)
 673         delay = ospf6->spf_delay;
 674       else
 675         delay = ht - elapsed;
 676     }
 677   else
 678     {
 679       /* Event is past required hold-time of last SPF */
 680       delay = ospf6->spf_delay;
 681       ospf6->spf_hold_multiplier = 1;
 682     }
 683
 684   if (IS_OSPF6_DEBUG_SPF(PROCESS) || IS_OSPF6_DEBUG_SPF (TIME))
 685     zlog_debug ("SPF: calculation timer delay = %ld", delay);
 686
 687   zlog_info ("SPF: Scheduled in %ld msec", delay);
 688
 689   ospf6->t_spf_calc =
 690     thread_add_timer_msec (master, ospf6_spf_calculation_thread, ospf6, delay);
 691 }
 692
 693 void
 694 ospf6_spf_display_subtree (struct vty *vty, const char *prefix, int rest,
 695                            struct ospf6_vertex *v)
 696 {
 697   struct listnode *node, *nnode;
 698   struct ospf6_vertex *c;
 699   char *next_prefix;
 700   int len;
 701   int restnum;
 702
 703   /* "prefix" is the space prefix of the display line */
 704   vty_out (vty, "%s+-%s [%d]%s", prefix, v->name, v->cost, VNL);
 705
 706   len = strlen (prefix) + 4;
 707   next_prefix = (char *) malloc (len);
 708   if (next_prefix == NULL)
 709     {
 710       vty_out (vty, "malloc failed%s", VNL);
 711       return;
 712     }
 713   snprintf (next_prefix, len, "%s%s", prefix, (rest ? "|  " : "   "));
 714
 715   restnum = listcount (v->child_list);
 716   for (ALL_LIST_ELEMENTS (v->child_list, node, nnode, c))
 717     {
 718       restnum--;
 719       ospf6_spf_display_subtree (vty, next_prefix, restnum, c);
 720     }
 721
 722   free (next_prefix);
 723 }
 724
 725 DEFUN (debug_ospf6_spf_process,
 726        debug_ospf6_spf_process_cmd,
 727        "debug ospf6 spf process",
 728        DEBUG_STR
 729        OSPF6_STR
 730        "Debug SPF Calculation\n"
 731        "Debug Detailed SPF Process\n"
 732       )
 733 {
 734   unsigned char level = 0;
 735   level = OSPF6_DEBUG_SPF_PROCESS;
 736   OSPF6_DEBUG_SPF_ON (level);
 737   return CMD_SUCCESS;
 738 }
 739
 740 DEFUN (debug_ospf6_spf_time,
 741        debug_ospf6_spf_time_cmd,
 742        "debug ospf6 spf time",
 743        DEBUG_STR
 744        OSPF6_STR
 745        "Debug SPF Calculation\n"
 746        "Measure time taken by SPF Calculation\n"
 747       )
 748 {
 749   unsigned char level = 0;
 750   level = OSPF6_DEBUG_SPF_TIME;
 751   OSPF6_DEBUG_SPF_ON (level);
 752   return CMD_SUCCESS;
 753 }
 754
 755 DEFUN (debug_ospf6_spf_database,
 756        debug_ospf6_spf_database_cmd,
 757        "debug ospf6 spf database",
 758        DEBUG_STR
 759        OSPF6_STR
 760        "Debug SPF Calculation\n"
 761        "Log number of LSAs at SPF Calculation time\n"
 762       )
 763 {
 764   unsigned char level = 0;
 765   level = OSPF6_DEBUG_SPF_DATABASE;
 766   OSPF6_DEBUG_SPF_ON (level);
 767   return CMD_SUCCESS;
 768 }
 769
 770 DEFUN (no_debug_ospf6_spf_process,
 771        no_debug_ospf6_spf_process_cmd,
 772        "no debug ospf6 spf process",
 773        NO_STR
 774        DEBUG_STR
 775        OSPF6_STR
 776        "Quit Debugging SPF Calculation\n"
 777        "Quit Debugging Detailed SPF Process\n"
 778       )
 779 {
 780   unsigned char level = 0;
 781   level = OSPF6_DEBUG_SPF_PROCESS;
 782   OSPF6_DEBUG_SPF_OFF (level);
 783   return CMD_SUCCESS;
 784 }
 785
 786 DEFUN (no_debug_ospf6_spf_time,
 787        no_debug_ospf6_spf_time_cmd,
 788        "no debug ospf6 spf time",
 789        NO_STR
 790        DEBUG_STR
 791        OSPF6_STR
 792        "Quit Debugging SPF Calculation\n"
 793        "Quit Measuring time taken by SPF Calculation\n"
 794       )
 795 {
 796   unsigned char level = 0;
 797   level = OSPF6_DEBUG_SPF_TIME;
 798   OSPF6_DEBUG_SPF_OFF (level);
 799   return CMD_SUCCESS;
 800 }
 801
 802 DEFUN (no_debug_ospf6_spf_database,
 803        no_debug_ospf6_spf_database_cmd,
 804        "no debug ospf6 spf database",
 805        NO_STR
 806        DEBUG_STR
 807        OSPF6_STR
 808        "Debug SPF Calculation\n"
 809        "Quit Logging number of LSAs at SPF Calculation time\n"
 810       )
 811 {
 812   unsigned char level = 0;
 813   level = OSPF6_DEBUG_SPF_DATABASE;
 814   OSPF6_DEBUG_SPF_OFF (level);
 815   return CMD_SUCCESS;
 816 }
 817
 818 static int
 819 ospf6_timers_spf_set (struct vty *vty, unsigned int delay,
 820                      unsigned int hold,
 821                      unsigned int max)
 822 {
 823   struct ospf6 *ospf = vty->index;
 824
 825   ospf->spf_delay = delay;
 826   ospf->spf_holdtime = hold;
 827   ospf->spf_max_holdtime = max;
 828
 829   return CMD_SUCCESS;
 830 }
 831
 832 DEFUN (ospf6_timers_throttle_spf,
 833        ospf6_timers_throttle_spf_cmd,
 834        "timers throttle spf <0-600000> <0-600000> <0-600000>",
 835        "Adjust routing timers\n"
 836        "Throttling adaptive timer\n"
 837        "OSPF6 SPF timers\n"
 838        "Delay (msec) from first change received till SPF calculation\n"
 839        "Initial hold time (msec) between consecutive SPF calculations\n"
 840        "Maximum hold time (msec)\n")
 841 {
 842   unsigned int delay, hold, max;
 843
 844   if (argc != 3)
 845     {
 846       vty_out (vty, "Insufficient arguments%s", VTY_NEWLINE);
 847       return CMD_WARNING;
 848     }
 849
 850   VTY_GET_INTEGER_RANGE ("SPF delay timer", delay, argv[0], 0, 600000);
 851   VTY_GET_INTEGER_RANGE ("SPF hold timer", hold, argv[1], 0, 600000);
 852   VTY_GET_INTEGER_RANGE ("SPF max-hold timer", max, argv[2], 0, 600000);
 853
 854   return ospf6_timers_spf_set (vty, delay, hold, max);
 855 }
 856
 857 DEFUN (no_ospf6_timers_throttle_spf,
 858        no_ospf6_timers_throttle_spf_cmd,
 859        "no timers throttle spf",
 860        NO_STR
 861        "Adjust routing timers\n"
 862        "Throttling adaptive timer\n"
 863        "OSPF6 SPF timers\n")
 864 {
 865   return ospf6_timers_spf_set (vty,
 866                               OSPF_SPF_DELAY_DEFAULT,
 867                               OSPF_SPF_HOLDTIME_DEFAULT,
 868                               OSPF_SPF_MAX_HOLDTIME_DEFAULT);
 869 }
 870
 871 int
 872 config_write_ospf6_debug_spf (struct vty *vty)
 873 {
 874   if (IS_OSPF6_DEBUG_SPF (PROCESS))
 875     vty_out (vty, "debug ospf6 spf process%s", VNL);
 876   if (IS_OSPF6_DEBUG_SPF (TIME))
 877     vty_out (vty, "debug ospf6 spf time%s", VNL);
 878   if (IS_OSPF6_DEBUG_SPF (DATABASE))
 879     vty_out (vty, "debug ospf6 spf database%s", VNL);
 880   return 0;
 881 }
 882
 883 void
 884 ospf6_spf_config_write (struct vty *vty)
 885 {
 886
 887   if (ospf6->spf_delay != OSPF_SPF_DELAY_DEFAULT ||
 888       ospf6->spf_holdtime != OSPF_SPF_HOLDTIME_DEFAULT ||
 889       ospf6->spf_max_holdtime != OSPF_SPF_MAX_HOLDTIME_DEFAULT)
 890     vty_out (vty, " timers throttle spf %d %d %d%s",
 891              ospf6->spf_delay, ospf6->spf_holdtime,
 892              ospf6->spf_max_holdtime, VTY_NEWLINE);
 893
 894 }
 895
 896 void
 897 install_element_ospf6_debug_spf (void)
 898 {
 899   install_element (ENABLE_NODE, &debug_ospf6_spf_process_cmd);
 900   install_element (ENABLE_NODE, &debug_ospf6_spf_time_cmd);
 901   install_element (ENABLE_NODE, &debug_ospf6_spf_database_cmd);
 902   install_element (ENABLE_NODE, &no_debug_ospf6_spf_process_cmd);
 903   install_element (ENABLE_NODE, &no_debug_ospf6_spf_time_cmd);
 904   install_element (ENABLE_NODE, &no_debug_ospf6_spf_database_cmd);
 905   install_element (CONFIG_NODE, &debug_ospf6_spf_process_cmd);
 906   install_element (CONFIG_NODE, &debug_ospf6_spf_time_cmd);
 907   install_element (CONFIG_NODE, &debug_ospf6_spf_database_cmd);
 908   install_element (CONFIG_NODE, &no_debug_ospf6_spf_process_cmd);
 909   install_element (CONFIG_NODE, &no_debug_ospf6_spf_time_cmd);
 910   install_element (CONFIG_NODE, &no_debug_ospf6_spf_database_cmd);
 911 }
 912
 913 void
 914 ospf6_spf_init (void)
 915 {
 916   install_element (OSPF6_NODE, &ospf6_timers_throttle_spf_cmd);
 917   install_element (OSPF6_NODE, &no_ospf6_timers_throttle_spf_cmd);
 918 }