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;
48 static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route
*rt
,
49 struct ospf6_vertex
*v
)
52 ospf6_copy_nexthops(rt
->nh_list
, v
->nh_list
);
55 static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route
*rt
,
56 struct ospf6_vertex
*v
)
59 ospf6_merge_nexthops(rt
->nh_list
, v
->nh_list
);
62 static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex
*v
)
64 struct ospf6_nexthop
*nh
;
65 struct listnode
*node
;
68 node
= listhead(v
->nh_list
);
70 nh
= listgetdata(node
);
78 static int ospf6_vertex_cmp(void *a
, void *b
)
80 struct ospf6_vertex
*va
= (struct ospf6_vertex
*)a
;
81 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*)b
;
84 if (va
->cost
!= vb
->cost
)
85 return (va
->cost
- vb
->cost
);
86 return (va
->hops
- vb
->hops
);
89 static int ospf6_vertex_id_cmp(void *a
, void *b
)
91 struct ospf6_vertex
*va
= (struct ospf6_vertex
*)a
;
92 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*)b
;
95 ret
= ntohl(ospf6_linkstate_prefix_adv_router(&va
->vertex_id
))
96 - ntohl(ospf6_linkstate_prefix_adv_router(&vb
->vertex_id
));
100 ret
= ntohl(ospf6_linkstate_prefix_id(&va
->vertex_id
))
101 - ntohl(ospf6_linkstate_prefix_id(&vb
->vertex_id
));
105 static struct ospf6_vertex
*ospf6_vertex_create(struct ospf6_lsa
*lsa
)
107 struct ospf6_vertex
*v
;
109 v
= (struct ospf6_vertex
*)XMALLOC(MTYPE_OSPF6_VERTEX
,
110 sizeof(struct ospf6_vertex
));
113 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
)
114 v
->type
= OSPF6_VERTEX_TYPE_ROUTER
;
115 else if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_NETWORK
)
116 v
->type
= OSPF6_VERTEX_TYPE_NETWORK
;
121 ospf6_linkstate_prefix(lsa
->header
->adv_router
, lsa
->header
->id
,
125 ospf6_linkstate_prefix2str(&v
->vertex_id
, v
->name
, sizeof(v
->name
));
127 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
128 zlog_debug("%s: Creating vertex %s of type %s", __func__
,
130 ((ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
)
137 /* capability bits + options */
138 v
->capability
= *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
));
139 v
->options
[0] = *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
) + 1);
140 v
->options
[1] = *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
) + 2);
141 v
->options
[2] = *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
) + 3);
143 v
->nh_list
= list_new();
144 v
->nh_list
->del
= (void (*) (void *))ospf6_nexthop_delete
;
147 v
->child_list
= list_new();
148 v
->child_list
->cmp
= ospf6_vertex_id_cmp
;
153 static void ospf6_vertex_delete(struct ospf6_vertex
*v
)
155 list_delete(v
->nh_list
);
156 list_delete(v
->child_list
);
157 XFREE(MTYPE_OSPF6_VERTEX
, v
);
160 static struct ospf6_lsa
*ospf6_lsdesc_lsa(caddr_t lsdesc
,
161 struct ospf6_vertex
*v
)
163 struct ospf6_lsa
*lsa
;
165 u_int32_t id
= 0, adv_router
= 0;
167 if (VERTEX_IS_TYPE(NETWORK
, v
)) {
168 type
= htons(OSPF6_LSTYPE_ROUTER
);
170 adv_router
= NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc
);
172 if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, lsdesc
)) {
173 type
= htons(OSPF6_LSTYPE_ROUTER
);
175 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
);
176 } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK
, lsdesc
)) {
177 type
= htons(OSPF6_LSTYPE_NETWORK
);
178 id
= htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc
));
179 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
);
183 lsa
= ospf6_lsdb_lookup(type
, id
, adv_router
, v
->area
->lsdb
);
185 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
186 char ibuf
[16], abuf
[16];
187 inet_ntop(AF_INET
, &id
, ibuf
, sizeof(ibuf
));
188 inet_ntop(AF_INET
, &adv_router
, abuf
, sizeof(abuf
));
190 zlog_debug(" Link to: %s", lsa
->name
);
192 zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA",
193 ospf6_lstype_name(type
), ibuf
, abuf
);
199 static char *ospf6_lsdesc_backlink(struct ospf6_lsa
*lsa
, caddr_t lsdesc
,
200 struct ospf6_vertex
*v
)
202 caddr_t backlink
, found
= NULL
;
205 size
= (OSPF6_LSA_IS_TYPE(ROUTER
, lsa
)
206 ? sizeof(struct ospf6_router_lsdesc
)
207 : sizeof(struct ospf6_network_lsdesc
));
208 for (backlink
= OSPF6_LSA_HEADER_END(lsa
->header
) + 4;
209 backlink
+ size
<= OSPF6_LSA_END(lsa
->header
); backlink
+= size
) {
210 assert(!(OSPF6_LSA_IS_TYPE(NETWORK
, lsa
)
211 && VERTEX_IS_TYPE(NETWORK
, v
)));
213 if (OSPF6_LSA_IS_TYPE(NETWORK
, lsa
)
214 && NETWORK_LSDESC_GET_NBR_ROUTERID(backlink
)
215 == v
->lsa
->header
->adv_router
)
217 else if (VERTEX_IS_TYPE(NETWORK
, v
)
218 && ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK
, backlink
)
219 && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink
)
220 == v
->lsa
->header
->adv_router
221 && ROUTER_LSDESC_GET_NBR_IFID(backlink
)
222 == ntohl(v
->lsa
->header
->id
))
225 if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, backlink
)
226 || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, lsdesc
))
228 if (ROUTER_LSDESC_GET_NBR_IFID(backlink
)
229 != ROUTER_LSDESC_GET_IFID(lsdesc
)
230 || ROUTER_LSDESC_GET_NBR_IFID(lsdesc
)
231 != ROUTER_LSDESC_GET_IFID(backlink
))
233 if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink
)
234 != v
->lsa
->header
->adv_router
235 || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
)
236 != lsa
->header
->adv_router
)
242 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
243 zlog_debug(" Backlink %s", (found
? "OK" : "FAIL"));
248 static void ospf6_nexthop_calc(struct ospf6_vertex
*w
, struct ospf6_vertex
*v
,
253 struct ospf6_interface
*oi
;
255 u_int32_t adv_router
;
256 struct ospf6_lsa
*lsa
;
257 struct ospf6_link_lsa
*link_lsa
;
260 assert(VERTEX_IS_TYPE(ROUTER
, w
));
261 ifindex
= (VERTEX_IS_TYPE(NETWORK
, v
) ? ospf6_spf_get_ifindex_from_nh(v
)
262 : ROUTER_LSDESC_GET_IFID(lsdesc
));
264 zlog_err("No nexthop ifindex at vertex %s", v
->name
);
268 oi
= ospf6_interface_lookup_by_ifindex(ifindex
);
270 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
271 zlog_debug("Can't find interface in SPF: ifindex %d",
276 type
= htons(OSPF6_LSTYPE_LINK
);
277 adv_router
= (VERTEX_IS_TYPE(NETWORK
, v
)
278 ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc
)
279 : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
));
282 for (ALL_LSDB_TYPED_ADVRTR(oi
->lsdb
, type
, adv_router
, lsa
)) {
283 if (VERTEX_IS_TYPE(ROUTER
, v
)
284 && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc
))
288 link_lsa
= (struct ospf6_link_lsa
*)OSPF6_LSA_HEADER_END(
290 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
291 inet_ntop(AF_INET6
, &link_lsa
->linklocal_addr
, buf
,
293 zlog_debug(" nexthop %s from %s", buf
, lsa
->name
);
296 ospf6_add_nexthop(w
->nh_list
, ifindex
,
297 &link_lsa
->linklocal_addr
);
301 if (i
== 0 && IS_OSPF6_DEBUG_SPF(PROCESS
))
302 zlog_debug("No nexthop for %s found", w
->name
);
305 static int ospf6_spf_install(struct ospf6_vertex
*v
,
306 struct ospf6_route_table
*result_table
)
308 struct ospf6_route
*route
, *parent_route
;
309 struct ospf6_vertex
*prev
;
311 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
312 zlog_debug("SPF install %s hops %d cost %d", v
->name
, v
->hops
,
315 route
= ospf6_route_lookup(&v
->vertex_id
, result_table
);
316 if (route
&& route
->path
.cost
< v
->cost
) {
317 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
319 " already installed with lower cost (%d), ignore",
321 ospf6_vertex_delete(v
);
323 } else if (route
&& route
->path
.cost
== v
->cost
) {
324 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
325 zlog_debug(" another path found, merge");
327 ospf6_spf_merge_nexthops_to_route(route
, v
);
329 prev
= (struct ospf6_vertex
*)route
->route_option
;
330 assert(prev
->hops
<= v
->hops
);
331 ospf6_vertex_delete(v
);
336 /* There should be no case where candidate being installed (variable
337 "v") is closer than the one in the SPF tree (variable "route").
338 In the case something has gone wrong with the behavior of
341 /* the case where the route exists already is handled and returned
343 assert(route
== NULL
);
345 route
= ospf6_route_create();
346 memcpy(&route
->prefix
, &v
->vertex_id
, sizeof(struct prefix
));
347 route
->type
= OSPF6_DEST_TYPE_LINKSTATE
;
348 route
->path
.type
= OSPF6_PATH_TYPE_INTRA
;
349 route
->path
.origin
.type
= v
->lsa
->header
->type
;
350 route
->path
.origin
.id
= v
->lsa
->header
->id
;
351 route
->path
.origin
.adv_router
= v
->lsa
->header
->adv_router
;
352 route
->path
.metric_type
= 1;
353 route
->path
.cost
= v
->cost
;
354 route
->path
.u
.cost_e2
= v
->hops
;
355 route
->path
.router_bits
= v
->capability
;
356 route
->path
.options
[0] = v
->options
[0];
357 route
->path
.options
[1] = v
->options
[1];
358 route
->path
.options
[2] = v
->options
[2];
360 ospf6_spf_copy_nexthops_to_route(route
, v
);
363 * The SPF logic implementation does not transfer the multipathing
365 * of a parent to a child node. Thus if there was a 3-way multipath to a
366 * node's parent and a single hop from the parent to the child, the
368 * creating new vertices and computing next hops prevents there from
370 * paths to the child node. This is primarily because the resolution of
371 * multipath is done in this routine, not in the main spf loop.
373 * The following logic addresses that problem by merging the parent's
375 * information with the child's, if the parent is not the root of the
377 * This is based on the assumption that before a node's route is
379 * its parent's route's nexthops have already been installed.
381 if (v
->parent
&& v
->parent
->hops
) {
383 ospf6_route_lookup(&v
->parent
->vertex_id
, result_table
);
385 ospf6_route_merge_nexthops(route
, parent_route
);
390 listnode_add_sort(v
->parent
->child_list
, v
);
391 route
->route_option
= v
;
393 ospf6_route_add(route
, result_table
);
397 void ospf6_spf_table_finish(struct ospf6_route_table
*result_table
)
399 struct ospf6_route
*route
, *nroute
;
400 struct ospf6_vertex
*v
;
401 for (route
= ospf6_route_head(result_table
); route
; route
= nroute
) {
402 nroute
= ospf6_route_next(route
);
403 v
= (struct ospf6_vertex
*)route
->route_option
;
404 ospf6_vertex_delete(v
);
405 ospf6_route_remove(route
, result_table
);
409 static const char *ospf6_spf_reason_str
[] = {
410 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
413 void ospf6_spf_reason_string(unsigned int reason
, char *buf
, int size
)
421 for (bit
= 0; bit
< array_size(ospf6_spf_reason_str
); bit
++) {
422 if ((reason
& (1 << bit
)) && (len
< size
)) {
423 len
+= snprintf((buf
+ len
), (size
- len
), "%s%s",
424 (len
> 0) ? ", " : "",
425 ospf6_spf_reason_str
[bit
]);
430 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
431 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
432 void ospf6_spf_calculation(u_int32_t router_id
,
433 struct ospf6_route_table
*result_table
,
434 struct ospf6_area
*oa
)
436 struct pqueue
*candidate_list
;
437 struct ospf6_vertex
*root
, *v
, *w
;
440 struct ospf6_lsa
*lsa
;
441 struct in6_addr address
;
443 ospf6_spf_table_finish(result_table
);
445 /* Install the calculating router itself as the root of the SPF tree */
446 /* construct root vertex */
447 lsa
= ospf6_lsdb_lookup(htons(OSPF6_LSTYPE_ROUTER
), htonl(0), router_id
,
450 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
451 zlog_debug("%s: No router LSA for area %s\n", __func__
,
457 candidate_list
= pqueue_create();
458 candidate_list
->cmp
= ospf6_vertex_cmp
;
460 root
= ospf6_vertex_create(lsa
);
464 inet_pton(AF_INET6
, "::1", &address
);
466 /* Actually insert root to the candidate-list as the only candidate */
467 pqueue_enqueue(root
, candidate_list
);
469 /* Iterate until candidate-list becomes empty */
470 while (candidate_list
->size
) {
471 /* get closest candidate from priority queue */
472 v
= pqueue_dequeue(candidate_list
);
474 /* installing may result in merging or rejecting of the vertex
476 if (ospf6_spf_install(v
, result_table
) < 0)
479 /* Skip overloaded routers */
480 if ((OSPF6_LSA_IS_TYPE(ROUTER
, v
->lsa
)
481 && ospf6_router_is_stub_router(v
->lsa
)))
484 /* For each LS description in the just-added vertex V's LSA */
485 size
= (VERTEX_IS_TYPE(ROUTER
, v
)
486 ? sizeof(struct ospf6_router_lsdesc
)
487 : sizeof(struct ospf6_network_lsdesc
));
488 for (lsdesc
= OSPF6_LSA_HEADER_END(v
->lsa
->header
) + 4;
489 lsdesc
+ size
<= OSPF6_LSA_END(v
->lsa
->header
);
491 lsa
= ospf6_lsdesc_lsa(lsdesc
, v
);
495 if (OSPF6_LSA_IS_MAXAGE(lsa
))
498 if (!ospf6_lsdesc_backlink(lsa
, lsdesc
, v
))
501 w
= ospf6_vertex_create(lsa
);
504 if (VERTEX_IS_TYPE(ROUTER
, v
)) {
506 + ROUTER_LSDESC_GET_METRIC(lsdesc
);
509 + (VERTEX_IS_TYPE(NETWORK
, w
) ? 0 : 1);
513 w
->hops
= v
->hops
+ 1;
516 /* nexthop calculation */
520 ROUTER_LSDESC_GET_IFID(lsdesc
), NULL
);
521 else if (w
->hops
== 1 && v
->hops
== 0)
522 ospf6_nexthop_calc(w
, v
, lsdesc
);
524 ospf6_copy_nexthops(w
->nh_list
, v
->nh_list
);
527 /* add new candidate to the candidate_list */
528 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
530 " New candidate: %s hops %d cost %d",
531 w
->name
, w
->hops
, w
->cost
);
532 pqueue_enqueue(w
, candidate_list
);
536 pqueue_delete(candidate_list
);
538 oa
->spf_calculation
++;
541 static void ospf6_spf_log_database(struct ospf6_area
*oa
)
543 char *p
, *end
, buffer
[256];
544 struct listnode
*node
;
545 struct ospf6_interface
*oi
;
548 end
= buffer
+ sizeof(buffer
);
550 snprintf(p
, end
- p
, "SPF on DB (#LSAs):");
551 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
552 snprintf(p
, end
- p
, " Area %s: %d", oa
->name
, oa
->lsdb
->count
);
553 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
555 for (ALL_LIST_ELEMENTS_RO(oa
->if_list
, node
, oi
)) {
556 snprintf(p
, end
- p
, " I/F %s: %d", oi
->interface
->name
,
558 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
)
562 zlog_debug("%s", buffer
);
565 static int ospf6_spf_calculation_thread(struct thread
*t
)
567 struct ospf6_area
*oa
;
569 struct timeval start
, end
, runtime
;
570 struct listnode
*node
;
571 int areas_processed
= 0;
574 ospf6
= (struct ospf6
*)THREAD_ARG(t
);
575 ospf6
->t_spf_calc
= NULL
;
577 /* execute SPF calculation */
580 if (ospf6_is_router_abr(ospf6
))
581 ospf6_abr_range_reset_cost(ospf6
);
583 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, node
, oa
)) {
585 if (oa
== ospf6
->backbone
)
588 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
589 zlog_debug("SPF calculation for Area %s", oa
->name
);
590 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
591 ospf6_spf_log_database(oa
);
593 ospf6_spf_calculation(ospf6
->router_id
, oa
->spf_table
, oa
);
594 ospf6_intra_route_calculation(oa
);
595 ospf6_intra_brouter_calculation(oa
);
600 if (ospf6
->backbone
) {
601 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
602 zlog_debug("SPF calculation for Backbone area %s",
603 ospf6
->backbone
->name
);
604 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
605 ospf6_spf_log_database(ospf6
->backbone
);
607 ospf6_spf_calculation(ospf6
->router_id
,
608 ospf6
->backbone
->spf_table
,
610 ospf6_intra_route_calculation(ospf6
->backbone
);
611 ospf6_intra_brouter_calculation(ospf6
->backbone
);
615 if (ospf6_is_router_abr(ospf6
))
616 ospf6_abr_defaults_to_stub(ospf6
);
619 timersub(&end
, &start
, &runtime
);
621 ospf6
->ts_spf_duration
= runtime
;
623 ospf6_spf_reason_string(ospf6
->spf_reason
, rbuf
, sizeof(rbuf
));
625 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
626 zlog_debug("SPF runtime: %lld sec %lld usec",
627 (long long)runtime
.tv_sec
,
628 (long long)runtime
.tv_usec
);
631 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
633 areas_processed
, (long long)runtime
.tv_sec
,
634 (long long)runtime
.tv_usec
, rbuf
);
635 ospf6
->last_spf_reason
= ospf6
->spf_reason
;
636 ospf6_reset_spf_reason(ospf6
);
640 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
641 set timer for SPF calc. */
642 void ospf6_spf_schedule(struct ospf6
*ospf6
, unsigned int reason
)
644 unsigned long delay
, elapsed
, ht
;
646 ospf6_set_spf_reason(ospf6
, reason
);
648 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
)) {
650 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
651 zlog_debug("SPF: calculation timer scheduled (reason %s)",
655 /* OSPF instance does not exist. */
659 /* SPF calculation timer is already scheduled. */
660 if (ospf6
->t_spf_calc
) {
661 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
663 "SPF: calculation timer is already scheduled: %p",
664 (void *)ospf6
->t_spf_calc
);
668 elapsed
= monotime_since(&ospf6
->ts_spf
, NULL
) / 1000LL;
669 ht
= ospf6
->spf_holdtime
* ospf6
->spf_hold_multiplier
;
671 if (ht
> ospf6
->spf_max_holdtime
)
672 ht
= ospf6
->spf_max_holdtime
;
674 /* Get SPF calculation delay time. */
676 /* Got an event within the hold time of last SPF. We need to
677 * increase the hold_multiplier, if it's not already at/past
678 * maximum value, and wasn't already increased..
680 if (ht
< ospf6
->spf_max_holdtime
)
681 ospf6
->spf_hold_multiplier
++;
683 /* always honour the SPF initial delay */
684 if ((ht
- elapsed
) < ospf6
->spf_delay
)
685 delay
= ospf6
->spf_delay
;
687 delay
= ht
- elapsed
;
689 /* Event is past required hold-time of last SPF */
690 delay
= ospf6
->spf_delay
;
691 ospf6
->spf_hold_multiplier
= 1;
694 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
695 zlog_debug("SPF: calculation timer delay = %ld", delay
);
697 zlog_info("SPF: Scheduled in %ld msec", delay
);
699 ospf6
->t_spf_calc
= NULL
;
700 thread_add_timer_msec(master
, ospf6_spf_calculation_thread
, ospf6
,
701 delay
, &ospf6
->t_spf_calc
);
704 void ospf6_spf_display_subtree(struct vty
*vty
, const char *prefix
, int rest
,
705 struct ospf6_vertex
*v
)
707 struct listnode
*node
, *nnode
;
708 struct ospf6_vertex
*c
;
713 /* "prefix" is the space prefix of the display line */
714 vty_out(vty
, "%s+-%s [%d]\n", prefix
, v
->name
, v
->cost
);
716 len
= strlen(prefix
) + 4;
717 next_prefix
= (char *)malloc(len
);
718 if (next_prefix
== NULL
) {
719 vty_out(vty
, "malloc failed\n");
722 snprintf(next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
724 restnum
= listcount(v
->child_list
);
725 for (ALL_LIST_ELEMENTS(v
->child_list
, node
, nnode
, c
)) {
727 ospf6_spf_display_subtree(vty
, next_prefix
, restnum
, c
);
733 DEFUN (debug_ospf6_spf_process
,
734 debug_ospf6_spf_process_cmd
,
735 "debug ospf6 spf process",
738 "Debug SPF Calculation\n"
739 "Debug Detailed SPF Process\n"
742 unsigned char level
= 0;
743 level
= OSPF6_DEBUG_SPF_PROCESS
;
744 OSPF6_DEBUG_SPF_ON(level
);
748 DEFUN (debug_ospf6_spf_time
,
749 debug_ospf6_spf_time_cmd
,
750 "debug ospf6 spf time",
753 "Debug SPF Calculation\n"
754 "Measure time taken by SPF Calculation\n"
757 unsigned char level
= 0;
758 level
= OSPF6_DEBUG_SPF_TIME
;
759 OSPF6_DEBUG_SPF_ON(level
);
763 DEFUN (debug_ospf6_spf_database
,
764 debug_ospf6_spf_database_cmd
,
765 "debug ospf6 spf database",
768 "Debug SPF Calculation\n"
769 "Log number of LSAs at SPF Calculation time\n"
772 unsigned char level
= 0;
773 level
= OSPF6_DEBUG_SPF_DATABASE
;
774 OSPF6_DEBUG_SPF_ON(level
);
778 DEFUN (no_debug_ospf6_spf_process
,
779 no_debug_ospf6_spf_process_cmd
,
780 "no debug ospf6 spf process",
784 "Quit Debugging SPF Calculation\n"
785 "Quit Debugging Detailed SPF Process\n"
788 unsigned char level
= 0;
789 level
= OSPF6_DEBUG_SPF_PROCESS
;
790 OSPF6_DEBUG_SPF_OFF(level
);
794 DEFUN (no_debug_ospf6_spf_time
,
795 no_debug_ospf6_spf_time_cmd
,
796 "no debug ospf6 spf time",
800 "Quit Debugging SPF Calculation\n"
801 "Quit Measuring time taken by SPF Calculation\n"
804 unsigned char level
= 0;
805 level
= OSPF6_DEBUG_SPF_TIME
;
806 OSPF6_DEBUG_SPF_OFF(level
);
810 DEFUN (no_debug_ospf6_spf_database
,
811 no_debug_ospf6_spf_database_cmd
,
812 "no debug ospf6 spf database",
816 "Debug SPF Calculation\n"
817 "Quit Logging number of LSAs at SPF Calculation time\n"
820 unsigned char level
= 0;
821 level
= OSPF6_DEBUG_SPF_DATABASE
;
822 OSPF6_DEBUG_SPF_OFF(level
);
826 static int ospf6_timers_spf_set(struct vty
*vty
, unsigned int delay
,
827 unsigned int hold
, unsigned int max
)
829 VTY_DECLVAR_CONTEXT(ospf6
, ospf
);
831 ospf
->spf_delay
= delay
;
832 ospf
->spf_holdtime
= hold
;
833 ospf
->spf_max_holdtime
= max
;
838 DEFUN (ospf6_timers_throttle_spf
,
839 ospf6_timers_throttle_spf_cmd
,
840 "timers throttle spf (0-600000) (0-600000) (0-600000)",
841 "Adjust routing timers\n"
842 "Throttling adaptive timer\n"
844 "Delay (msec) from first change received till SPF calculation\n"
845 "Initial hold time (msec) between consecutive SPF calculations\n"
846 "Maximum hold time (msec)\n")
849 int idx_number_2
= 4;
850 int idx_number_3
= 5;
851 unsigned int delay
, hold
, max
;
853 delay
= strtoul(argv
[idx_number
]->arg
, NULL
, 10);
854 hold
= strtoul(argv
[idx_number_2
]->arg
, NULL
, 10);
855 max
= strtoul(argv
[idx_number_3
]->arg
, NULL
, 10);
857 return ospf6_timers_spf_set(vty
, delay
, hold
, max
);
860 DEFUN (no_ospf6_timers_throttle_spf
,
861 no_ospf6_timers_throttle_spf_cmd
,
862 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
864 "Adjust routing timers\n"
865 "Throttling adaptive timer\n"
867 "Delay (msec) from first change received till SPF calculation\n"
868 "Initial hold time (msec) between consecutive SPF calculations\n"
869 "Maximum hold time (msec)\n")
871 return ospf6_timers_spf_set(vty
, OSPF_SPF_DELAY_DEFAULT
,
872 OSPF_SPF_HOLDTIME_DEFAULT
,
873 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
877 int config_write_ospf6_debug_spf(struct vty
*vty
)
879 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
880 vty_out(vty
, "debug ospf6 spf process\n");
881 if (IS_OSPF6_DEBUG_SPF(TIME
))
882 vty_out(vty
, "debug ospf6 spf time\n");
883 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
884 vty_out(vty
, "debug ospf6 spf database\n");
888 void ospf6_spf_config_write(struct vty
*vty
)
891 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
892 || ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
893 || ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
894 vty_out(vty
, " timers throttle spf %d %d %d\n",
895 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
896 ospf6
->spf_max_holdtime
);
899 void install_element_ospf6_debug_spf(void)
901 install_element(ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
902 install_element(ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
903 install_element(ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
904 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
905 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
906 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
907 install_element(CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
908 install_element(CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
909 install_element(CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
910 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
911 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
912 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
915 void ospf6_spf_init(void)
917 install_element(OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
918 install_element(OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);