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