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 */
579 ospf6
->ts_spf
= start
;
581 if (ospf6_is_router_abr(ospf6
))
582 ospf6_abr_range_reset_cost(ospf6
);
584 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, node
, oa
)) {
586 if (oa
== ospf6
->backbone
)
589 monotime(&oa
->ts_spf
);
590 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
591 zlog_debug("SPF calculation for Area %s", oa
->name
);
592 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
593 ospf6_spf_log_database(oa
);
595 ospf6_spf_calculation(ospf6
->router_id
, oa
->spf_table
, oa
);
596 ospf6_intra_route_calculation(oa
);
597 ospf6_intra_brouter_calculation(oa
);
602 if (ospf6
->backbone
) {
603 monotime(&ospf6
->backbone
->ts_spf
);
604 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
605 zlog_debug("SPF calculation for Backbone area %s",
606 ospf6
->backbone
->name
);
607 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
608 ospf6_spf_log_database(ospf6
->backbone
);
610 ospf6_spf_calculation(ospf6
->router_id
,
611 ospf6
->backbone
->spf_table
,
613 ospf6_intra_route_calculation(ospf6
->backbone
);
614 ospf6_intra_brouter_calculation(ospf6
->backbone
);
618 if (ospf6_is_router_abr(ospf6
))
619 ospf6_abr_defaults_to_stub(ospf6
);
622 timersub(&end
, &start
, &runtime
);
624 ospf6
->ts_spf_duration
= runtime
;
626 ospf6_spf_reason_string(ospf6
->spf_reason
, rbuf
, sizeof(rbuf
));
628 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
629 zlog_debug("SPF runtime: %lld sec %lld usec",
630 (long long)runtime
.tv_sec
,
631 (long long)runtime
.tv_usec
);
634 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
636 areas_processed
, (long long)runtime
.tv_sec
,
637 (long long)runtime
.tv_usec
, rbuf
);
639 ospf6
->last_spf_reason
= ospf6
->spf_reason
;
640 ospf6_reset_spf_reason(ospf6
);
644 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
645 set timer for SPF calc. */
646 void ospf6_spf_schedule(struct ospf6
*ospf6
, unsigned int reason
)
648 unsigned long delay
, elapsed
, ht
;
650 ospf6_set_spf_reason(ospf6
, reason
);
652 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
)) {
654 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
655 zlog_debug("SPF: calculation timer scheduled (reason %s)",
659 /* OSPF instance does not exist. */
663 /* SPF calculation timer is already scheduled. */
664 if (ospf6
->t_spf_calc
) {
665 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
667 "SPF: calculation timer is already scheduled: %p",
668 (void *)ospf6
->t_spf_calc
);
672 elapsed
= monotime_since(&ospf6
->ts_spf
, NULL
) / 1000LL;
673 ht
= ospf6
->spf_holdtime
* ospf6
->spf_hold_multiplier
;
675 if (ht
> ospf6
->spf_max_holdtime
)
676 ht
= ospf6
->spf_max_holdtime
;
678 /* Get SPF calculation delay time. */
680 /* Got an event within the hold time of last SPF. We need to
681 * increase the hold_multiplier, if it's not already at/past
682 * maximum value, and wasn't already increased..
684 if (ht
< ospf6
->spf_max_holdtime
)
685 ospf6
->spf_hold_multiplier
++;
687 /* always honour the SPF initial delay */
688 if ((ht
- elapsed
) < ospf6
->spf_delay
)
689 delay
= ospf6
->spf_delay
;
691 delay
= ht
- elapsed
;
693 /* Event is past required hold-time of last SPF */
694 delay
= ospf6
->spf_delay
;
695 ospf6
->spf_hold_multiplier
= 1;
698 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
699 zlog_debug("SPF: calculation timer delay = %ld", delay
);
701 zlog_info("SPF: Scheduled in %ld msec", delay
);
703 ospf6
->t_spf_calc
= NULL
;
704 thread_add_timer_msec(master
, ospf6_spf_calculation_thread
, ospf6
,
705 delay
, &ospf6
->t_spf_calc
);
708 void ospf6_spf_display_subtree(struct vty
*vty
, const char *prefix
, int rest
,
709 struct ospf6_vertex
*v
)
711 struct listnode
*node
, *nnode
;
712 struct ospf6_vertex
*c
;
717 /* "prefix" is the space prefix of the display line */
718 vty_out(vty
, "%s+-%s [%d]\n", prefix
, v
->name
, v
->cost
);
720 len
= strlen(prefix
) + 4;
721 next_prefix
= (char *)malloc(len
);
722 if (next_prefix
== NULL
) {
723 vty_out(vty
, "malloc failed\n");
726 snprintf(next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
728 restnum
= listcount(v
->child_list
);
729 for (ALL_LIST_ELEMENTS(v
->child_list
, node
, nnode
, c
)) {
731 ospf6_spf_display_subtree(vty
, next_prefix
, restnum
, c
);
737 DEFUN (debug_ospf6_spf_process
,
738 debug_ospf6_spf_process_cmd
,
739 "debug ospf6 spf process",
742 "Debug SPF Calculation\n"
743 "Debug Detailed SPF Process\n"
746 unsigned char level
= 0;
747 level
= OSPF6_DEBUG_SPF_PROCESS
;
748 OSPF6_DEBUG_SPF_ON(level
);
752 DEFUN (debug_ospf6_spf_time
,
753 debug_ospf6_spf_time_cmd
,
754 "debug ospf6 spf time",
757 "Debug SPF Calculation\n"
758 "Measure time taken by SPF Calculation\n"
761 unsigned char level
= 0;
762 level
= OSPF6_DEBUG_SPF_TIME
;
763 OSPF6_DEBUG_SPF_ON(level
);
767 DEFUN (debug_ospf6_spf_database
,
768 debug_ospf6_spf_database_cmd
,
769 "debug ospf6 spf database",
772 "Debug SPF Calculation\n"
773 "Log number of LSAs at SPF Calculation time\n"
776 unsigned char level
= 0;
777 level
= OSPF6_DEBUG_SPF_DATABASE
;
778 OSPF6_DEBUG_SPF_ON(level
);
782 DEFUN (no_debug_ospf6_spf_process
,
783 no_debug_ospf6_spf_process_cmd
,
784 "no debug ospf6 spf process",
788 "Quit Debugging SPF Calculation\n"
789 "Quit Debugging Detailed SPF Process\n"
792 unsigned char level
= 0;
793 level
= OSPF6_DEBUG_SPF_PROCESS
;
794 OSPF6_DEBUG_SPF_OFF(level
);
798 DEFUN (no_debug_ospf6_spf_time
,
799 no_debug_ospf6_spf_time_cmd
,
800 "no debug ospf6 spf time",
804 "Quit Debugging SPF Calculation\n"
805 "Quit Measuring time taken by SPF Calculation\n"
808 unsigned char level
= 0;
809 level
= OSPF6_DEBUG_SPF_TIME
;
810 OSPF6_DEBUG_SPF_OFF(level
);
814 DEFUN (no_debug_ospf6_spf_database
,
815 no_debug_ospf6_spf_database_cmd
,
816 "no debug ospf6 spf database",
820 "Debug SPF Calculation\n"
821 "Quit Logging number of LSAs at SPF Calculation time\n"
824 unsigned char level
= 0;
825 level
= OSPF6_DEBUG_SPF_DATABASE
;
826 OSPF6_DEBUG_SPF_OFF(level
);
830 static int ospf6_timers_spf_set(struct vty
*vty
, unsigned int delay
,
831 unsigned int hold
, unsigned int max
)
833 VTY_DECLVAR_CONTEXT(ospf6
, ospf
);
835 ospf
->spf_delay
= delay
;
836 ospf
->spf_holdtime
= hold
;
837 ospf
->spf_max_holdtime
= max
;
842 DEFUN (ospf6_timers_throttle_spf
,
843 ospf6_timers_throttle_spf_cmd
,
844 "timers throttle spf (0-600000) (0-600000) (0-600000)",
845 "Adjust routing timers\n"
846 "Throttling adaptive timer\n"
848 "Delay (msec) from first change received till SPF calculation\n"
849 "Initial hold time (msec) between consecutive SPF calculations\n"
850 "Maximum hold time (msec)\n")
853 int idx_number_2
= 4;
854 int idx_number_3
= 5;
855 unsigned int delay
, hold
, max
;
857 delay
= strtoul(argv
[idx_number
]->arg
, NULL
, 10);
858 hold
= strtoul(argv
[idx_number_2
]->arg
, NULL
, 10);
859 max
= strtoul(argv
[idx_number_3
]->arg
, NULL
, 10);
861 return ospf6_timers_spf_set(vty
, delay
, hold
, max
);
864 DEFUN (no_ospf6_timers_throttle_spf
,
865 no_ospf6_timers_throttle_spf_cmd
,
866 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
868 "Adjust routing timers\n"
869 "Throttling adaptive timer\n"
871 "Delay (msec) from first change received till SPF calculation\n"
872 "Initial hold time (msec) between consecutive SPF calculations\n"
873 "Maximum hold time (msec)\n")
875 return ospf6_timers_spf_set(vty
, OSPF_SPF_DELAY_DEFAULT
,
876 OSPF_SPF_HOLDTIME_DEFAULT
,
877 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
881 int config_write_ospf6_debug_spf(struct vty
*vty
)
883 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
884 vty_out(vty
, "debug ospf6 spf process\n");
885 if (IS_OSPF6_DEBUG_SPF(TIME
))
886 vty_out(vty
, "debug ospf6 spf time\n");
887 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
888 vty_out(vty
, "debug ospf6 spf database\n");
892 void ospf6_spf_config_write(struct vty
*vty
)
895 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
896 || ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
897 || ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
898 vty_out(vty
, " timers throttle spf %d %d %d\n",
899 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
900 ospf6
->spf_max_holdtime
);
903 void install_element_ospf6_debug_spf(void)
905 install_element(ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
906 install_element(ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
907 install_element(ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
908 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
909 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
910 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
911 install_element(CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
912 install_element(CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
913 install_element(CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
914 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
915 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
916 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
919 void ospf6_spf_init(void)
921 install_element(OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
922 install_element(OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);