2 * Copyright (C) 2003 Yasuhiro Ohara
4 * This file is part of GNU Zebra.
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
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.
16 * You should have received a copy of the GNU General Public License along
17 * with this program; see the file COPYING; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
21 /* Shortest Path First calculation for OSPFv3 */
34 #include "ospf6_lsa.h"
35 #include "ospf6_lsdb.h"
36 #include "ospf6_route.h"
37 #include "ospf6_area.h"
38 #include "ospf6_proto.h"
39 #include "ospf6_abr.h"
40 #include "ospf6_spf.h"
41 #include "ospf6_intra.h"
42 #include "ospf6_interface.h"
44 #include "ospf6_abr.h"
46 unsigned char conf_debug_ospf6_spf
= 0;
49 ospf6_spf_copy_nexthops_to_route (struct ospf6_route
*rt
,
50 struct ospf6_vertex
*v
)
53 ospf6_copy_nexthops (rt
->nh_list
, v
->nh_list
);
57 ospf6_spf_merge_nexthops_to_route (struct ospf6_route
*rt
,
58 struct ospf6_vertex
*v
)
61 ospf6_merge_nexthops (rt
->nh_list
, v
->nh_list
);
65 ospf6_spf_get_ifindex_from_nh (struct ospf6_vertex
*v
)
67 struct ospf6_nexthop
*nh
;
68 struct listnode
*node
;
72 node
= listhead(v
->nh_list
);
75 nh
= listgetdata (node
);
84 ospf6_vertex_cmp (void *a
, void *b
)
86 struct ospf6_vertex
*va
= (struct ospf6_vertex
*) a
;
87 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*) b
;
90 if (va
->cost
!= vb
->cost
)
91 return (va
->cost
- vb
->cost
);
92 return (va
->hops
- vb
->hops
);
96 ospf6_vertex_id_cmp (void *a
, void *b
)
98 struct ospf6_vertex
*va
= (struct ospf6_vertex
*) a
;
99 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*) b
;
102 ret
= ntohl (ospf6_linkstate_prefix_adv_router (&va
->vertex_id
)) -
103 ntohl (ospf6_linkstate_prefix_adv_router (&vb
->vertex_id
));
107 ret
= ntohl (ospf6_linkstate_prefix_id (&va
->vertex_id
)) -
108 ntohl (ospf6_linkstate_prefix_id (&vb
->vertex_id
));
112 static struct ospf6_vertex
*
113 ospf6_vertex_create (struct ospf6_lsa
*lsa
)
115 struct ospf6_vertex
*v
;
117 v
= (struct ospf6_vertex
*)
118 XMALLOC (MTYPE_OSPF6_VERTEX
, sizeof (struct ospf6_vertex
));
121 if (ntohs (lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
)
122 v
->type
= OSPF6_VERTEX_TYPE_ROUTER
;
123 else if (ntohs (lsa
->header
->type
) == OSPF6_LSTYPE_NETWORK
)
124 v
->type
= OSPF6_VERTEX_TYPE_NETWORK
;
129 ospf6_linkstate_prefix (lsa
->header
->adv_router
, lsa
->header
->id
,
133 ospf6_linkstate_prefix2str (&v
->vertex_id
, v
->name
, sizeof (v
->name
));
135 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
136 zlog_debug ("%s: Creating vertex %s of type %s", __func__
, v
->name
,
137 ((ntohs (lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
) ? "Router" : "N/W"));
142 /* capability bits + options */
143 v
->capability
= *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
));
144 v
->options
[0] = *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
) + 1);
145 v
->options
[1] = *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
) + 2);
146 v
->options
[2] = *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
) + 3);
148 v
->nh_list
= list_new();
151 v
->child_list
= list_new ();
152 v
->child_list
->cmp
= ospf6_vertex_id_cmp
;
158 ospf6_vertex_delete (struct ospf6_vertex
*v
)
160 list_delete(v
->nh_list
);
161 list_delete (v
->child_list
);
162 XFREE (MTYPE_OSPF6_VERTEX
, v
);
165 static struct ospf6_lsa
*
166 ospf6_lsdesc_lsa (caddr_t lsdesc
, struct ospf6_vertex
*v
)
168 struct ospf6_lsa
*lsa
;
170 u_int32_t id
= 0, adv_router
= 0;
172 if (VERTEX_IS_TYPE (NETWORK
, v
))
174 type
= htons (OSPF6_LSTYPE_ROUTER
);
176 adv_router
= NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc
);
180 if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, lsdesc
))
182 type
= htons (OSPF6_LSTYPE_ROUTER
);
184 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
);
186 else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK
, lsdesc
))
188 type
= htons (OSPF6_LSTYPE_NETWORK
);
189 id
= htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc
));
190 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
);
194 lsa
= ospf6_lsdb_lookup (type
, id
, adv_router
, v
->area
->lsdb
);
196 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
198 char ibuf
[16], abuf
[16];
199 inet_ntop (AF_INET
, &id
, ibuf
, sizeof (ibuf
));
200 inet_ntop (AF_INET
, &adv_router
, abuf
, sizeof (abuf
));
202 zlog_debug (" Link to: %s", lsa
->name
);
204 zlog_debug (" Link to: [%s Id:%s Adv:%s] No LSA",
205 ospf6_lstype_name (type
), ibuf
, abuf
);
212 ospf6_lsdesc_backlink (struct ospf6_lsa
*lsa
,
213 caddr_t lsdesc
, struct ospf6_vertex
*v
)
215 caddr_t backlink
, found
= NULL
;
218 size
= (OSPF6_LSA_IS_TYPE (ROUTER
, lsa
) ?
219 sizeof (struct ospf6_router_lsdesc
) :
220 sizeof (struct ospf6_network_lsdesc
));
221 for (backlink
= OSPF6_LSA_HEADER_END (lsa
->header
) + 4;
222 backlink
+ size
<= OSPF6_LSA_END (lsa
->header
); backlink
+= size
)
224 assert (! (OSPF6_LSA_IS_TYPE (NETWORK
, lsa
) &&
225 VERTEX_IS_TYPE (NETWORK
, v
)));
227 if (OSPF6_LSA_IS_TYPE (NETWORK
, lsa
) &&
228 NETWORK_LSDESC_GET_NBR_ROUTERID (backlink
)
229 == v
->lsa
->header
->adv_router
)
231 else if (VERTEX_IS_TYPE (NETWORK
, v
) &&
232 ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK
, backlink
) &&
233 ROUTER_LSDESC_GET_NBR_ROUTERID (backlink
)
234 == v
->lsa
->header
->adv_router
&&
235 ROUTER_LSDESC_GET_NBR_IFID (backlink
)
236 == ntohl (v
->lsa
->header
->id
))
240 if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, backlink
) ||
241 ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, lsdesc
))
243 if (ROUTER_LSDESC_GET_NBR_IFID (backlink
) !=
244 ROUTER_LSDESC_GET_IFID (lsdesc
) ||
245 ROUTER_LSDESC_GET_NBR_IFID (lsdesc
) !=
246 ROUTER_LSDESC_GET_IFID (backlink
))
248 if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink
) !=
249 v
->lsa
->header
->adv_router
||
250 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
) !=
251 lsa
->header
->adv_router
)
257 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
258 zlog_debug (" Backlink %s", (found
? "OK" : "FAIL"));
264 ospf6_nexthop_calc (struct ospf6_vertex
*w
, struct ospf6_vertex
*v
,
269 struct ospf6_interface
*oi
;
271 u_int32_t adv_router
;
272 struct ospf6_lsa
*lsa
;
273 struct ospf6_link_lsa
*link_lsa
;
276 assert (VERTEX_IS_TYPE (ROUTER
, w
));
277 ifindex
= (VERTEX_IS_TYPE (NETWORK
, v
) ? ospf6_spf_get_ifindex_from_nh (v
) :
278 ROUTER_LSDESC_GET_IFID (lsdesc
));
281 zlog_err ("No nexthop ifindex at vertex %s", v
->name
);
285 oi
= ospf6_interface_lookup_by_ifindex (ifindex
);
288 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
289 zlog_debug ("Can't find interface in SPF: ifindex %d", ifindex
);
293 type
= htons (OSPF6_LSTYPE_LINK
);
294 adv_router
= (VERTEX_IS_TYPE (NETWORK
, v
) ?
295 NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc
) :
296 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
));
299 for (ALL_LSDB_TYPED_ADVRTR(oi
->lsdb
, type
, adv_router
, lsa
))
301 if (VERTEX_IS_TYPE (ROUTER
, v
) &&
302 htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc
)) != lsa
->header
->id
)
305 link_lsa
= (struct ospf6_link_lsa
*) OSPF6_LSA_HEADER_END (lsa
->header
);
306 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
308 inet_ntop (AF_INET6
, &link_lsa
->linklocal_addr
, buf
, sizeof (buf
));
309 zlog_debug (" nexthop %s from %s", buf
, lsa
->name
);
312 ospf6_add_nexthop (w
->nh_list
, ifindex
, &link_lsa
->linklocal_addr
);
316 if (i
== 0 && IS_OSPF6_DEBUG_SPF (PROCESS
))
317 zlog_debug ("No nexthop for %s found", w
->name
);
321 ospf6_spf_install (struct ospf6_vertex
*v
,
322 struct ospf6_route_table
*result_table
)
324 struct ospf6_route
*route
, *parent_route
;
325 struct ospf6_vertex
*prev
;
327 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
328 zlog_debug ("SPF install %s hops %d cost %d",
329 v
->name
, v
->hops
, v
->cost
);
331 route
= ospf6_route_lookup (&v
->vertex_id
, result_table
);
332 if (route
&& route
->path
.cost
< v
->cost
)
334 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
335 zlog_debug (" already installed with lower cost (%d), ignore",
337 ospf6_vertex_delete (v
);
340 else if (route
&& route
->path
.cost
== v
->cost
)
342 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
343 zlog_debug (" another path found, merge");
345 ospf6_spf_merge_nexthops_to_route (route
, v
);
347 prev
= (struct ospf6_vertex
*) route
->route_option
;
348 assert (prev
->hops
<= v
->hops
);
349 ospf6_vertex_delete (v
);
354 /* There should be no case where candidate being installed (variable
355 "v") is closer than the one in the SPF tree (variable "route").
356 In the case something has gone wrong with the behavior of
359 /* the case where the route exists already is handled and returned
361 assert (route
== NULL
);
363 route
= ospf6_route_create ();
364 memcpy (&route
->prefix
, &v
->vertex_id
, sizeof (struct prefix
));
365 route
->type
= OSPF6_DEST_TYPE_LINKSTATE
;
366 route
->path
.type
= OSPF6_PATH_TYPE_INTRA
;
367 route
->path
.origin
.type
= v
->lsa
->header
->type
;
368 route
->path
.origin
.id
= v
->lsa
->header
->id
;
369 route
->path
.origin
.adv_router
= v
->lsa
->header
->adv_router
;
370 route
->path
.metric_type
= 1;
371 route
->path
.cost
= v
->cost
;
372 route
->path
.u
.cost_e2
= v
->hops
;
373 route
->path
.router_bits
= v
->capability
;
374 route
->path
.options
[0] = v
->options
[0];
375 route
->path
.options
[1] = v
->options
[1];
376 route
->path
.options
[2] = v
->options
[2];
378 ospf6_spf_copy_nexthops_to_route (route
, v
);
381 * The SPF logic implementation does not transfer the multipathing properties
382 * of a parent to a child node. Thus if there was a 3-way multipath to a
383 * node's parent and a single hop from the parent to the child, the logic of
384 * creating new vertices and computing next hops prevents there from being 3
385 * paths to the child node. This is primarily because the resolution of
386 * multipath is done in this routine, not in the main spf loop.
388 * The following logic addresses that problem by merging the parent's nexthop
389 * information with the child's, if the parent is not the root of the tree.
390 * This is based on the assumption that before a node's route is installed,
391 * its parent's route's nexthops have already been installed.
393 if (v
->parent
&& v
->parent
->hops
)
395 parent_route
= ospf6_route_lookup (&v
->parent
->vertex_id
, result_table
);
398 ospf6_route_merge_nexthops (route
, parent_route
);
403 listnode_add_sort (v
->parent
->child_list
, v
);
404 route
->route_option
= v
;
406 ospf6_route_add (route
, result_table
);
411 ospf6_spf_table_finish (struct ospf6_route_table
*result_table
)
413 struct ospf6_route
*route
, *nroute
;
414 struct ospf6_vertex
*v
;
415 for (route
= ospf6_route_head (result_table
); route
;
418 nroute
= ospf6_route_next (route
);
419 v
= (struct ospf6_vertex
*) route
->route_option
;
420 ospf6_vertex_delete (v
);
421 ospf6_route_remove (route
, result_table
);
425 static const char *ospf6_spf_reason_str
[] =
437 void ospf6_spf_reason_string (unsigned int reason
, char *buf
, int size
)
445 for (bit
= 0; bit
< array_size(ospf6_spf_reason_str
); bit
++)
447 if ((reason
& (1 << bit
)) && (len
< size
))
449 len
+= snprintf((buf
+ len
), (size
- len
), "%s%s",
450 (len
> 0) ? ", " : "", ospf6_spf_reason_str
[bit
]);
455 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
456 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
458 ospf6_spf_calculation (u_int32_t router_id
,
459 struct ospf6_route_table
*result_table
,
460 struct ospf6_area
*oa
)
462 struct pqueue
*candidate_list
;
463 struct ospf6_vertex
*root
, *v
, *w
;
466 struct ospf6_lsa
*lsa
;
467 struct in6_addr address
;
469 ospf6_spf_table_finish (result_table
);
471 /* Install the calculating router itself as the root of the SPF tree */
472 /* construct root vertex */
473 lsa
= ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER
), htonl (0),
474 router_id
, oa
->lsdb_self
);
477 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
478 zlog_debug ("%s: No router LSA for area %s\n",
484 candidate_list
= pqueue_create ();
485 candidate_list
->cmp
= ospf6_vertex_cmp
;
487 root
= ospf6_vertex_create (lsa
);
491 inet_pton (AF_INET6
, "::1", &address
);
493 /* Actually insert root to the candidate-list as the only candidate */
494 pqueue_enqueue (root
, candidate_list
);
496 /* Iterate until candidate-list becomes empty */
497 while (candidate_list
->size
)
499 /* get closest candidate from priority queue */
500 v
= pqueue_dequeue (candidate_list
);
502 /* installing may result in merging or rejecting of the vertex */
503 if (ospf6_spf_install (v
, result_table
) < 0)
506 /* Skip overloaded routers */
507 if ((OSPF6_LSA_IS_TYPE (ROUTER
, v
->lsa
) &&
508 ospf6_router_is_stub_router (v
->lsa
)))
511 /* For each LS description in the just-added vertex V's LSA */
512 size
= (VERTEX_IS_TYPE (ROUTER
, v
) ?
513 sizeof (struct ospf6_router_lsdesc
) :
514 sizeof (struct ospf6_network_lsdesc
));
515 for (lsdesc
= OSPF6_LSA_HEADER_END (v
->lsa
->header
) + 4;
516 lsdesc
+ size
<= OSPF6_LSA_END (v
->lsa
->header
); lsdesc
+= size
)
518 lsa
= ospf6_lsdesc_lsa (lsdesc
, v
);
522 if (OSPF6_LSA_IS_MAXAGE (lsa
))
525 if (! ospf6_lsdesc_backlink (lsa
, lsdesc
, v
))
528 w
= ospf6_vertex_create (lsa
);
531 if (VERTEX_IS_TYPE (ROUTER
, v
))
533 w
->cost
= v
->cost
+ ROUTER_LSDESC_GET_METRIC (lsdesc
);
534 w
->hops
= v
->hops
+ (VERTEX_IS_TYPE (NETWORK
, w
) ? 0 : 1);
539 w
->hops
= v
->hops
+ 1;
542 /* nexthop calculation */
544 ospf6_add_nexthop (w
->nh_list
, ROUTER_LSDESC_GET_IFID (lsdesc
), NULL
);
545 else if (w
->hops
== 1 && v
->hops
== 0)
546 ospf6_nexthop_calc (w
, v
, lsdesc
);
549 ospf6_copy_nexthops (w
->nh_list
, v
->nh_list
);
552 /* add new candidate to the candidate_list */
553 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
554 zlog_debug (" New candidate: %s hops %d cost %d",
555 w
->name
, w
->hops
, w
->cost
);
556 pqueue_enqueue (w
, candidate_list
);
560 pqueue_delete (candidate_list
);
562 oa
->spf_calculation
++;
566 ospf6_spf_log_database (struct ospf6_area
*oa
)
568 char *p
, *end
, buffer
[256];
569 struct listnode
*node
;
570 struct ospf6_interface
*oi
;
573 end
= buffer
+ sizeof (buffer
);
575 snprintf (p
, end
- p
, "SPF on DB (#LSAs):");
576 p
= (buffer
+ strlen (buffer
) < end
? buffer
+ strlen (buffer
) : end
);
577 snprintf (p
, end
- p
, " Area %s: %d", oa
->name
, oa
->lsdb
->count
);
578 p
= (buffer
+ strlen (buffer
) < end
? buffer
+ strlen (buffer
) : end
);
580 for (ALL_LIST_ELEMENTS_RO (oa
->if_list
, node
, oi
))
582 snprintf (p
, end
- p
, " I/F %s: %d",
583 oi
->interface
->name
, oi
->lsdb
->count
);
584 p
= (buffer
+ strlen (buffer
) < end
? buffer
+ strlen (buffer
) : end
);
587 zlog_debug ("%s", buffer
);
591 ospf6_spf_calculation_thread (struct thread
*t
)
593 struct ospf6_area
*oa
;
595 struct timeval start
, end
, runtime
;
596 struct listnode
*node
;
597 int areas_processed
= 0;
600 ospf6
= (struct ospf6
*)THREAD_ARG (t
);
601 ospf6
->t_spf_calc
= NULL
;
603 /* execute SPF calculation */
606 if (ospf6_is_router_abr (ospf6
))
607 ospf6_abr_range_reset_cost (ospf6
);
609 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, node
, oa
))
612 if (oa
== ospf6
->backbone
)
615 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
616 zlog_debug ("SPF calculation for Area %s", oa
->name
);
617 if (IS_OSPF6_DEBUG_SPF (DATABASE
))
618 ospf6_spf_log_database (oa
);
620 ospf6_spf_calculation (ospf6
->router_id
, oa
->spf_table
, oa
);
621 ospf6_intra_route_calculation (oa
);
622 ospf6_intra_brouter_calculation (oa
);
629 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
630 zlog_debug ("SPF calculation for Backbone area %s",
631 ospf6
->backbone
->name
);
632 if (IS_OSPF6_DEBUG_SPF (DATABASE
))
633 ospf6_spf_log_database(ospf6
->backbone
);
635 ospf6_spf_calculation(ospf6
->router_id
, ospf6
->backbone
->spf_table
,
637 ospf6_intra_route_calculation(ospf6
->backbone
);
638 ospf6_intra_brouter_calculation(ospf6
->backbone
);
642 if (ospf6_is_router_abr (ospf6
))
643 ospf6_abr_defaults_to_stub (ospf6
);
646 timersub (&end
, &start
, &runtime
);
648 ospf6
->ts_spf_duration
= runtime
;
650 ospf6_spf_reason_string(ospf6
->spf_reason
, rbuf
, sizeof(rbuf
));
652 if (IS_OSPF6_DEBUG_SPF (PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
653 zlog_debug ("SPF runtime: %lld sec %lld usec",
654 (long long)runtime
.tv_sec
, (long long)runtime
.tv_usec
);
656 zlog_info("SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
657 "Reason: %s\n", areas_processed
,
658 (long long)runtime
.tv_sec
, (long long)runtime
.tv_usec
,
660 ospf6
->last_spf_reason
= ospf6
->spf_reason
;
661 ospf6_reset_spf_reason(ospf6
);
665 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
666 set timer for SPF calc. */
668 ospf6_spf_schedule (struct ospf6
*ospf6
, unsigned int reason
)
670 unsigned long delay
, elapsed
, ht
;
672 ospf6_set_spf_reason(ospf6
, reason
);
674 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
677 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
678 zlog_debug ("SPF: calculation timer scheduled (reason %s)", rbuf
);
681 /* OSPF instance does not exist. */
685 /* SPF calculation timer is already scheduled. */
686 if (ospf6
->t_spf_calc
)
688 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
689 zlog_debug ("SPF: calculation timer is already scheduled: %p",
690 (void *)ospf6
->t_spf_calc
);
694 elapsed
= monotime_since(&ospf6
->ts_spf
, NULL
) / 1000LL;
695 ht
= ospf6
->spf_holdtime
* ospf6
->spf_hold_multiplier
;
697 if (ht
> ospf6
->spf_max_holdtime
)
698 ht
= ospf6
->spf_max_holdtime
;
700 /* Get SPF calculation delay time. */
703 /* Got an event within the hold time of last SPF. We need to
704 * increase the hold_multiplier, if it's not already at/past
705 * maximum value, and wasn't already increased..
707 if (ht
< ospf6
->spf_max_holdtime
)
708 ospf6
->spf_hold_multiplier
++;
710 /* always honour the SPF initial delay */
711 if ( (ht
- elapsed
) < ospf6
->spf_delay
)
712 delay
= ospf6
->spf_delay
;
714 delay
= ht
- elapsed
;
718 /* Event is past required hold-time of last SPF */
719 delay
= ospf6
->spf_delay
;
720 ospf6
->spf_hold_multiplier
= 1;
723 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
724 zlog_debug ("SPF: calculation timer delay = %ld", delay
);
726 zlog_info ("SPF: Scheduled in %ld msec", delay
);
728 ospf6
->t_spf_calc
= NULL
;
729 thread_add_timer_msec(master
, ospf6_spf_calculation_thread
, ospf6
, delay
,
734 ospf6_spf_display_subtree (struct vty
*vty
, const char *prefix
, int rest
,
735 struct ospf6_vertex
*v
)
737 struct listnode
*node
, *nnode
;
738 struct ospf6_vertex
*c
;
743 /* "prefix" is the space prefix of the display line */
744 vty_out (vty
, "%s+-%s [%d]\n", prefix
, v
->name
, v
->cost
);
746 len
= strlen (prefix
) + 4;
747 next_prefix
= (char *) malloc (len
);
748 if (next_prefix
== NULL
)
750 vty_out (vty
, "malloc failed\n");
753 snprintf (next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
755 restnum
= listcount (v
->child_list
);
756 for (ALL_LIST_ELEMENTS (v
->child_list
, node
, nnode
, c
))
759 ospf6_spf_display_subtree (vty
, next_prefix
, restnum
, c
);
765 DEFUN (debug_ospf6_spf_process
,
766 debug_ospf6_spf_process_cmd
,
767 "debug ospf6 spf process",
770 "Debug SPF Calculation\n"
771 "Debug Detailed SPF Process\n"
774 unsigned char level
= 0;
775 level
= OSPF6_DEBUG_SPF_PROCESS
;
776 OSPF6_DEBUG_SPF_ON (level
);
780 DEFUN (debug_ospf6_spf_time
,
781 debug_ospf6_spf_time_cmd
,
782 "debug ospf6 spf time",
785 "Debug SPF Calculation\n"
786 "Measure time taken by SPF Calculation\n"
789 unsigned char level
= 0;
790 level
= OSPF6_DEBUG_SPF_TIME
;
791 OSPF6_DEBUG_SPF_ON (level
);
795 DEFUN (debug_ospf6_spf_database
,
796 debug_ospf6_spf_database_cmd
,
797 "debug ospf6 spf database",
800 "Debug SPF Calculation\n"
801 "Log number of LSAs at SPF Calculation time\n"
804 unsigned char level
= 0;
805 level
= OSPF6_DEBUG_SPF_DATABASE
;
806 OSPF6_DEBUG_SPF_ON (level
);
810 DEFUN (no_debug_ospf6_spf_process
,
811 no_debug_ospf6_spf_process_cmd
,
812 "no debug ospf6 spf process",
816 "Quit Debugging SPF Calculation\n"
817 "Quit Debugging Detailed SPF Process\n"
820 unsigned char level
= 0;
821 level
= OSPF6_DEBUG_SPF_PROCESS
;
822 OSPF6_DEBUG_SPF_OFF (level
);
826 DEFUN (no_debug_ospf6_spf_time
,
827 no_debug_ospf6_spf_time_cmd
,
828 "no debug ospf6 spf time",
832 "Quit Debugging SPF Calculation\n"
833 "Quit Measuring time taken by SPF Calculation\n"
836 unsigned char level
= 0;
837 level
= OSPF6_DEBUG_SPF_TIME
;
838 OSPF6_DEBUG_SPF_OFF (level
);
842 DEFUN (no_debug_ospf6_spf_database
,
843 no_debug_ospf6_spf_database_cmd
,
844 "no debug ospf6 spf database",
848 "Debug SPF Calculation\n"
849 "Quit Logging number of LSAs at SPF Calculation time\n"
852 unsigned char level
= 0;
853 level
= OSPF6_DEBUG_SPF_DATABASE
;
854 OSPF6_DEBUG_SPF_OFF (level
);
859 ospf6_timers_spf_set (struct vty
*vty
, unsigned int delay
,
863 VTY_DECLVAR_CONTEXT(ospf6
, ospf
);
865 ospf
->spf_delay
= delay
;
866 ospf
->spf_holdtime
= hold
;
867 ospf
->spf_max_holdtime
= max
;
872 DEFUN (ospf6_timers_throttle_spf
,
873 ospf6_timers_throttle_spf_cmd
,
874 "timers throttle spf (0-600000) (0-600000) (0-600000)",
875 "Adjust routing timers\n"
876 "Throttling adaptive timer\n"
878 "Delay (msec) from first change received till SPF calculation\n"
879 "Initial hold time (msec) between consecutive SPF calculations\n"
880 "Maximum hold time (msec)\n")
883 int idx_number_2
= 4;
884 int idx_number_3
= 5;
885 unsigned int delay
, hold
, max
;
887 delay
= strtoul(argv
[idx_number
]->arg
, NULL
, 10);
888 hold
= strtoul(argv
[idx_number_2
]->arg
, NULL
, 10);
889 max
= strtoul(argv
[idx_number_3
]->arg
, NULL
, 10);
891 return ospf6_timers_spf_set (vty
, delay
, hold
, max
);
894 DEFUN (no_ospf6_timers_throttle_spf
,
895 no_ospf6_timers_throttle_spf_cmd
,
896 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
898 "Adjust routing timers\n"
899 "Throttling adaptive timer\n"
901 "Delay (msec) from first change received till SPF calculation\n"
902 "Initial hold time (msec) between consecutive SPF calculations\n"
903 "Maximum hold time (msec)\n")
905 return ospf6_timers_spf_set (vty
,
906 OSPF_SPF_DELAY_DEFAULT
,
907 OSPF_SPF_HOLDTIME_DEFAULT
,
908 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
913 config_write_ospf6_debug_spf (struct vty
*vty
)
915 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
916 vty_out (vty
, "debug ospf6 spf process\n");
917 if (IS_OSPF6_DEBUG_SPF (TIME
))
918 vty_out (vty
, "debug ospf6 spf time\n");
919 if (IS_OSPF6_DEBUG_SPF (DATABASE
))
920 vty_out (vty
, "debug ospf6 spf database\n");
925 ospf6_spf_config_write (struct vty
*vty
)
928 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
||
929 ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
||
930 ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
931 vty_out (vty
, " timers throttle spf %d %d %d\n",
932 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
933 ospf6
->spf_max_holdtime
);
938 install_element_ospf6_debug_spf (void)
940 install_element (ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
941 install_element (ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
942 install_element (ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
943 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
944 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
945 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
946 install_element (CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
947 install_element (CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
948 install_element (CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
949 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
950 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
951 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
955 ospf6_spf_init (void)
957 install_element (OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
958 install_element (OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);