]> git.sommitrealweird.co.uk Git - quagga-debian.git/blob - ospf6d/ospf6_spf.c
New upstream version 1.2.4
[quagga-debian.git] / 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 }