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
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.
22 /* Shortest Path First calculation for OSPFv3 */
35 #include "ospf6_lsa.h"
36 #include "ospf6_lsdb.h"
37 #include "ospf6_route.h"
38 #include "ospf6_area.h"
39 #include "ospf6_proto.h"
40 #include "ospf6_abr.h"
41 #include "ospf6_spf.h"
42 #include "ospf6_intra.h"
43 #include "ospf6_interface.h"
45 #include "ospf6_abr.h"
47 unsigned char conf_debug_ospf6_spf
= 0;
50 ospf6_spf_copy_nexthops_to_route (struct ospf6_route
*rt
,
51 struct ospf6_vertex
*v
)
54 ospf6_copy_nexthops (rt
->nh_list
, v
->nh_list
);
58 ospf6_spf_merge_nexthops_to_route (struct ospf6_route
*rt
,
59 struct ospf6_vertex
*v
)
62 ospf6_merge_nexthops (rt
->nh_list
, v
->nh_list
);
66 ospf6_spf_get_ifindex_from_nh (struct ospf6_vertex
*v
)
68 struct ospf6_nexthop
*nh
;
69 struct listnode
*node
;
73 node
= listhead(v
->nh_list
);
76 nh
= listgetdata (node
);
85 ospf6_vertex_cmp (void *a
, void *b
)
87 struct ospf6_vertex
*va
= (struct ospf6_vertex
*) a
;
88 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*) b
;
91 if (va
->cost
!= vb
->cost
)
92 return (va
->cost
- vb
->cost
);
93 return (va
->hops
- vb
->hops
);
97 ospf6_vertex_id_cmp (void *a
, void *b
)
99 struct ospf6_vertex
*va
= (struct ospf6_vertex
*) a
;
100 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*) b
;
103 ret
= ntohl (ospf6_linkstate_prefix_adv_router (&va
->vertex_id
)) -
104 ntohl (ospf6_linkstate_prefix_adv_router (&vb
->vertex_id
));
108 ret
= ntohl (ospf6_linkstate_prefix_id (&va
->vertex_id
)) -
109 ntohl (ospf6_linkstate_prefix_id (&vb
->vertex_id
));
113 static struct ospf6_vertex
*
114 ospf6_vertex_create (struct ospf6_lsa
*lsa
)
116 struct ospf6_vertex
*v
;
118 v
= (struct ospf6_vertex
*)
119 XMALLOC (MTYPE_OSPF6_VERTEX
, sizeof (struct ospf6_vertex
));
122 if (ntohs (lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
)
123 v
->type
= OSPF6_VERTEX_TYPE_ROUTER
;
124 else if (ntohs (lsa
->header
->type
) == OSPF6_LSTYPE_NETWORK
)
125 v
->type
= OSPF6_VERTEX_TYPE_NETWORK
;
130 ospf6_linkstate_prefix (lsa
->header
->adv_router
, lsa
->header
->id
,
134 ospf6_linkstate_prefix2str (&v
->vertex_id
, v
->name
, sizeof (v
->name
));
136 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
137 zlog_debug ("%s: Creating vertex %s of type %s", __func__
, v
->name
,
138 ((ntohs (lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
) ? "Router" : "N/W"));
143 /* capability bits + options */
144 v
->capability
= *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
));
145 v
->options
[0] = *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
) + 1);
146 v
->options
[1] = *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
) + 2);
147 v
->options
[2] = *(u_char
*)(OSPF6_LSA_HEADER_END (lsa
->header
) + 3);
149 v
->nh_list
= list_new();
152 v
->child_list
= list_new ();
153 v
->child_list
->cmp
= ospf6_vertex_id_cmp
;
159 ospf6_vertex_delete (struct ospf6_vertex
*v
)
161 list_delete(v
->nh_list
);
162 list_delete (v
->child_list
);
163 XFREE (MTYPE_OSPF6_VERTEX
, v
);
166 static struct ospf6_lsa
*
167 ospf6_lsdesc_lsa (caddr_t lsdesc
, struct ospf6_vertex
*v
)
169 struct ospf6_lsa
*lsa
;
171 u_int32_t id
= 0, adv_router
= 0;
173 if (VERTEX_IS_TYPE (NETWORK
, v
))
175 type
= htons (OSPF6_LSTYPE_ROUTER
);
177 adv_router
= NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc
);
181 if (ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, lsdesc
))
183 type
= htons (OSPF6_LSTYPE_ROUTER
);
185 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
);
187 else if (ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK
, lsdesc
))
189 type
= htons (OSPF6_LSTYPE_NETWORK
);
190 id
= htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc
));
191 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
);
195 lsa
= ospf6_lsdb_lookup (type
, id
, adv_router
, v
->area
->lsdb
);
197 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
199 char ibuf
[16], abuf
[16];
200 inet_ntop (AF_INET
, &id
, ibuf
, sizeof (ibuf
));
201 inet_ntop (AF_INET
, &adv_router
, abuf
, sizeof (abuf
));
203 zlog_debug (" Link to: %s", lsa
->name
);
205 zlog_debug (" Link to: [%s Id:%s Adv:%s] No LSA",
206 ospf6_lstype_name (type
), ibuf
, abuf
);
213 ospf6_lsdesc_backlink (struct ospf6_lsa
*lsa
,
214 caddr_t lsdesc
, struct ospf6_vertex
*v
)
216 caddr_t backlink
, found
= NULL
;
219 size
= (OSPF6_LSA_IS_TYPE (ROUTER
, lsa
) ?
220 sizeof (struct ospf6_router_lsdesc
) :
221 sizeof (struct ospf6_network_lsdesc
));
222 for (backlink
= OSPF6_LSA_HEADER_END (lsa
->header
) + 4;
223 backlink
+ size
<= OSPF6_LSA_END (lsa
->header
); backlink
+= size
)
225 assert (! (OSPF6_LSA_IS_TYPE (NETWORK
, lsa
) &&
226 VERTEX_IS_TYPE (NETWORK
, v
)));
228 if (OSPF6_LSA_IS_TYPE (NETWORK
, lsa
) &&
229 NETWORK_LSDESC_GET_NBR_ROUTERID (backlink
)
230 == v
->lsa
->header
->adv_router
)
232 else if (VERTEX_IS_TYPE (NETWORK
, v
) &&
233 ROUTER_LSDESC_IS_TYPE (TRANSIT_NETWORK
, backlink
) &&
234 ROUTER_LSDESC_GET_NBR_ROUTERID (backlink
)
235 == v
->lsa
->header
->adv_router
&&
236 ROUTER_LSDESC_GET_NBR_IFID (backlink
)
237 == ntohl (v
->lsa
->header
->id
))
241 if (! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, backlink
) ||
242 ! ROUTER_LSDESC_IS_TYPE (POINTTOPOINT
, lsdesc
))
244 if (ROUTER_LSDESC_GET_NBR_IFID (backlink
) !=
245 ROUTER_LSDESC_GET_IFID (lsdesc
) ||
246 ROUTER_LSDESC_GET_NBR_IFID (lsdesc
) !=
247 ROUTER_LSDESC_GET_IFID (backlink
))
249 if (ROUTER_LSDESC_GET_NBR_ROUTERID (backlink
) !=
250 v
->lsa
->header
->adv_router
||
251 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
) !=
252 lsa
->header
->adv_router
)
258 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
259 zlog_debug (" Backlink %s", (found
? "OK" : "FAIL"));
265 ospf6_nexthop_calc (struct ospf6_vertex
*w
, struct ospf6_vertex
*v
,
270 struct ospf6_interface
*oi
;
272 u_int32_t adv_router
;
273 struct ospf6_lsa
*lsa
;
274 struct ospf6_link_lsa
*link_lsa
;
277 assert (VERTEX_IS_TYPE (ROUTER
, w
));
278 ifindex
= (VERTEX_IS_TYPE (NETWORK
, v
) ? ospf6_spf_get_ifindex_from_nh (v
) :
279 ROUTER_LSDESC_GET_IFID (lsdesc
));
282 zlog_err ("No nexthop ifindex at vertex %s", v
->name
);
286 oi
= ospf6_interface_lookup_by_ifindex (ifindex
);
289 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
290 zlog_debug ("Can't find interface in SPF: ifindex %d", ifindex
);
294 type
= htons (OSPF6_LSTYPE_LINK
);
295 adv_router
= (VERTEX_IS_TYPE (NETWORK
, v
) ?
296 NETWORK_LSDESC_GET_NBR_ROUTERID (lsdesc
) :
297 ROUTER_LSDESC_GET_NBR_ROUTERID (lsdesc
));
300 for (lsa
= ospf6_lsdb_type_router_head (type
, adv_router
, oi
->lsdb
); lsa
;
301 lsa
= ospf6_lsdb_type_router_next (type
, adv_router
, lsa
))
303 if (VERTEX_IS_TYPE (ROUTER
, v
) &&
304 htonl (ROUTER_LSDESC_GET_NBR_IFID (lsdesc
)) != lsa
->header
->id
)
307 link_lsa
= (struct ospf6_link_lsa
*) OSPF6_LSA_HEADER_END (lsa
->header
);
308 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
310 inet_ntop (AF_INET6
, &link_lsa
->linklocal_addr
, buf
, sizeof (buf
));
311 zlog_debug (" nexthop %s from %s", buf
, lsa
->name
);
314 ospf6_add_nexthop (w
->nh_list
, ifindex
, &link_lsa
->linklocal_addr
);
318 if (i
== 0 && IS_OSPF6_DEBUG_SPF (PROCESS
))
319 zlog_debug ("No nexthop for %s found", w
->name
);
323 ospf6_spf_install (struct ospf6_vertex
*v
,
324 struct ospf6_route_table
*result_table
)
326 struct ospf6_route
*route
, *parent_route
;
327 struct ospf6_vertex
*prev
;
329 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
330 zlog_debug ("SPF install %s hops %d cost %d",
331 v
->name
, v
->hops
, v
->cost
);
333 route
= ospf6_route_lookup (&v
->vertex_id
, result_table
);
334 if (route
&& route
->path
.cost
< v
->cost
)
336 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
337 zlog_debug (" already installed with lower cost (%d), ignore",
339 ospf6_vertex_delete (v
);
342 else if (route
&& route
->path
.cost
== v
->cost
)
344 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
345 zlog_debug (" another path found, merge");
347 ospf6_spf_merge_nexthops_to_route (route
, v
);
349 prev
= (struct ospf6_vertex
*) route
->route_option
;
350 assert (prev
->hops
<= v
->hops
);
351 ospf6_vertex_delete (v
);
356 /* There should be no case where candidate being installed (variable
357 "v") is closer than the one in the SPF tree (variable "route").
358 In the case something has gone wrong with the behavior of
361 /* the case where the route exists already is handled and returned
363 assert (route
== NULL
);
365 route
= ospf6_route_create ();
366 memcpy (&route
->prefix
, &v
->vertex_id
, sizeof (struct prefix
));
367 route
->type
= OSPF6_DEST_TYPE_LINKSTATE
;
368 route
->path
.type
= OSPF6_PATH_TYPE_INTRA
;
369 route
->path
.origin
.type
= v
->lsa
->header
->type
;
370 route
->path
.origin
.id
= v
->lsa
->header
->id
;
371 route
->path
.origin
.adv_router
= v
->lsa
->header
->adv_router
;
372 route
->path
.metric_type
= 1;
373 route
->path
.cost
= v
->cost
;
374 route
->path
.u
.cost_e2
= v
->hops
;
375 route
->path
.router_bits
= v
->capability
;
376 route
->path
.options
[0] = v
->options
[0];
377 route
->path
.options
[1] = v
->options
[1];
378 route
->path
.options
[2] = v
->options
[2];
380 ospf6_spf_copy_nexthops_to_route (route
, v
);
383 * The SPF logic implementation does not transfer the multipathing properties
384 * of a parent to a child node. Thus if there was a 3-way multipath to a
385 * node's parent and a single hop from the parent to the child, the logic of
386 * creating new vertices and computing next hops prevents there from being 3
387 * paths to the child node. This is primarily because the resolution of
388 * multipath is done in this routine, not in the main spf loop.
390 * The following logic addresses that problem by merging the parent's nexthop
391 * information with the child's, if the parent is not the root of the tree.
392 * This is based on the assumption that before a node's route is installed,
393 * its parent's route's nexthops have already been installed.
395 if (v
->parent
&& v
->parent
->hops
)
397 parent_route
= ospf6_route_lookup (&v
->parent
->vertex_id
, result_table
);
400 ospf6_route_merge_nexthops (route
, parent_route
);
405 listnode_add_sort (v
->parent
->child_list
, v
);
406 route
->route_option
= v
;
408 ospf6_route_add (route
, result_table
);
413 ospf6_spf_table_finish (struct ospf6_route_table
*result_table
)
415 struct ospf6_route
*route
, *nroute
;
416 struct ospf6_vertex
*v
;
417 for (route
= ospf6_route_head (result_table
); route
;
420 nroute
= ospf6_route_next (route
);
421 v
= (struct ospf6_vertex
*) route
->route_option
;
422 ospf6_vertex_delete (v
);
423 ospf6_route_remove (route
, result_table
);
427 static const char *ospf6_spf_reason_str
[] =
439 void ospf6_spf_reason_string (unsigned int reason
, char *buf
, int size
)
447 for (bit
= 0; bit
< array_size(ospf6_spf_reason_str
); bit
++)
449 if ((reason
& (1 << bit
)) && (len
< size
))
451 len
+= snprintf((buf
+ len
), (size
- len
), "%s%s",
452 (len
> 0) ? ", " : "", ospf6_spf_reason_str
[bit
]);
457 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
458 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
460 ospf6_spf_calculation (u_int32_t router_id
,
461 struct ospf6_route_table
*result_table
,
462 struct ospf6_area
*oa
)
464 struct pqueue
*candidate_list
;
465 struct ospf6_vertex
*root
, *v
, *w
;
468 struct ospf6_lsa
*lsa
;
469 struct in6_addr address
;
471 ospf6_spf_table_finish (result_table
);
473 /* Install the calculating router itself as the root of the SPF tree */
474 /* construct root vertex */
475 lsa
= ospf6_lsdb_lookup (htons (OSPF6_LSTYPE_ROUTER
), htonl (0),
476 router_id
, oa
->lsdb_self
);
479 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
480 zlog_debug ("%s: No router LSA for area %s\n",
486 candidate_list
= pqueue_create ();
487 candidate_list
->cmp
= ospf6_vertex_cmp
;
489 root
= ospf6_vertex_create (lsa
);
493 inet_pton (AF_INET6
, "::1", &address
);
495 /* Actually insert root to the candidate-list as the only candidate */
496 pqueue_enqueue (root
, candidate_list
);
498 /* Iterate until candidate-list becomes empty */
499 while (candidate_list
->size
)
501 /* get closest candidate from priority queue */
502 v
= pqueue_dequeue (candidate_list
);
504 /* installing may result in merging or rejecting of the vertex */
505 if (ospf6_spf_install (v
, result_table
) < 0)
508 /* Skip overloaded routers */
509 if ((OSPF6_LSA_IS_TYPE (ROUTER
, v
->lsa
) &&
510 ospf6_router_is_stub_router (v
->lsa
)))
513 /* For each LS description in the just-added vertex V's LSA */
514 size
= (VERTEX_IS_TYPE (ROUTER
, v
) ?
515 sizeof (struct ospf6_router_lsdesc
) :
516 sizeof (struct ospf6_network_lsdesc
));
517 for (lsdesc
= OSPF6_LSA_HEADER_END (v
->lsa
->header
) + 4;
518 lsdesc
+ size
<= OSPF6_LSA_END (v
->lsa
->header
); lsdesc
+= size
)
520 lsa
= ospf6_lsdesc_lsa (lsdesc
, v
);
524 if (OSPF6_LSA_IS_MAXAGE (lsa
))
527 if (! ospf6_lsdesc_backlink (lsa
, lsdesc
, v
))
530 w
= ospf6_vertex_create (lsa
);
533 if (VERTEX_IS_TYPE (ROUTER
, v
))
535 w
->cost
= v
->cost
+ ROUTER_LSDESC_GET_METRIC (lsdesc
);
536 w
->hops
= v
->hops
+ (VERTEX_IS_TYPE (NETWORK
, w
) ? 0 : 1);
541 w
->hops
= v
->hops
+ 1;
544 /* nexthop calculation */
546 ospf6_add_nexthop (w
->nh_list
, ROUTER_LSDESC_GET_IFID (lsdesc
), NULL
);
547 else if (w
->hops
== 1 && v
->hops
== 0)
548 ospf6_nexthop_calc (w
, v
, lsdesc
);
551 ospf6_copy_nexthops (w
->nh_list
, v
->nh_list
);
554 /* add new candidate to the candidate_list */
555 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
556 zlog_debug (" New candidate: %s hops %d cost %d",
557 w
->name
, w
->hops
, w
->cost
);
558 pqueue_enqueue (w
, candidate_list
);
562 pqueue_delete (candidate_list
);
564 oa
->spf_calculation
++;
568 ospf6_spf_log_database (struct ospf6_area
*oa
)
570 char *p
, *end
, buffer
[256];
571 struct listnode
*node
;
572 struct ospf6_interface
*oi
;
575 end
= buffer
+ sizeof (buffer
);
577 snprintf (p
, end
- p
, "SPF on DB (#LSAs):");
578 p
= (buffer
+ strlen (buffer
) < end
? buffer
+ strlen (buffer
) : end
);
579 snprintf (p
, end
- p
, " Area %s: %d", oa
->name
, oa
->lsdb
->count
);
580 p
= (buffer
+ strlen (buffer
) < end
? buffer
+ strlen (buffer
) : end
);
582 for (ALL_LIST_ELEMENTS_RO (oa
->if_list
, node
, oi
))
584 snprintf (p
, end
- p
, " I/F %s: %d",
585 oi
->interface
->name
, oi
->lsdb
->count
);
586 p
= (buffer
+ strlen (buffer
) < end
? buffer
+ strlen (buffer
) : end
);
589 zlog_debug ("%s", buffer
);
593 ospf6_spf_calculation_thread (struct thread
*t
)
595 struct ospf6_area
*oa
;
597 struct timeval start
, end
, runtime
;
598 struct listnode
*node
;
599 int areas_processed
= 0;
602 ospf6
= (struct ospf6
*)THREAD_ARG (t
);
603 ospf6
->t_spf_calc
= NULL
;
605 /* execute SPF calculation */
608 if (ospf6_is_router_abr (ospf6
))
609 ospf6_abr_range_reset_cost (ospf6
);
611 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, node
, oa
))
614 if (oa
== ospf6
->backbone
)
617 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
618 zlog_debug ("SPF calculation for Area %s", oa
->name
);
619 if (IS_OSPF6_DEBUG_SPF (DATABASE
))
620 ospf6_spf_log_database (oa
);
622 ospf6_spf_calculation (ospf6
->router_id
, oa
->spf_table
, oa
);
623 ospf6_intra_route_calculation (oa
);
624 ospf6_intra_brouter_calculation (oa
);
631 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
632 zlog_debug ("SPF calculation for Backbone area %s",
633 ospf6
->backbone
->name
);
634 if (IS_OSPF6_DEBUG_SPF (DATABASE
))
635 ospf6_spf_log_database(ospf6
->backbone
);
637 ospf6_spf_calculation(ospf6
->router_id
, ospf6
->backbone
->spf_table
,
639 ospf6_intra_route_calculation(ospf6
->backbone
);
640 ospf6_intra_brouter_calculation(ospf6
->backbone
);
644 if (ospf6_is_router_abr (ospf6
))
645 ospf6_abr_defaults_to_stub (ospf6
);
648 timersub (&end
, &start
, &runtime
);
650 ospf6
->ts_spf_duration
= runtime
;
652 ospf6_spf_reason_string(ospf6
->spf_reason
, rbuf
, sizeof(rbuf
));
654 if (IS_OSPF6_DEBUG_SPF (PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
655 zlog_debug ("SPF runtime: %lld sec %lld usec",
656 (long long)runtime
.tv_sec
, (long long)runtime
.tv_usec
);
658 zlog_info("SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
659 "Reason: %s\n", areas_processed
,
660 (long long)runtime
.tv_sec
, (long long)runtime
.tv_usec
,
662 ospf6
->last_spf_reason
= ospf6
->spf_reason
;
663 ospf6_reset_spf_reason(ospf6
);
667 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
668 set timer for SPF calc. */
670 ospf6_spf_schedule (struct ospf6
*ospf6
, unsigned int reason
)
672 unsigned long delay
, elapsed
, ht
;
674 ospf6_set_spf_reason(ospf6
, reason
);
676 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
679 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
680 zlog_debug ("SPF: calculation timer scheduled (reason %s)", rbuf
);
683 /* OSPF instance does not exist. */
687 /* SPF calculation timer is already scheduled. */
688 if (ospf6
->t_spf_calc
)
690 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
691 zlog_debug ("SPF: calculation timer is already scheduled: %p",
692 (void *)ospf6
->t_spf_calc
);
696 elapsed
= monotime_since(&ospf6
->ts_spf
, NULL
) / 1000LL;
697 ht
= ospf6
->spf_holdtime
* ospf6
->spf_hold_multiplier
;
699 if (ht
> ospf6
->spf_max_holdtime
)
700 ht
= ospf6
->spf_max_holdtime
;
702 /* Get SPF calculation delay time. */
705 /* Got an event within the hold time of last SPF. We need to
706 * increase the hold_multiplier, if it's not already at/past
707 * maximum value, and wasn't already increased..
709 if (ht
< ospf6
->spf_max_holdtime
)
710 ospf6
->spf_hold_multiplier
++;
712 /* always honour the SPF initial delay */
713 if ( (ht
- elapsed
) < ospf6
->spf_delay
)
714 delay
= ospf6
->spf_delay
;
716 delay
= ht
- elapsed
;
720 /* Event is past required hold-time of last SPF */
721 delay
= ospf6
->spf_delay
;
722 ospf6
->spf_hold_multiplier
= 1;
725 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
726 zlog_debug ("SPF: calculation timer delay = %ld", delay
);
728 zlog_info ("SPF: Scheduled in %ld msec", delay
);
730 ospf6
->t_spf_calc
= NULL
;
731 thread_add_timer_msec(master
, ospf6_spf_calculation_thread
, ospf6
, delay
,
736 ospf6_spf_display_subtree (struct vty
*vty
, const char *prefix
, int rest
,
737 struct ospf6_vertex
*v
)
739 struct listnode
*node
, *nnode
;
740 struct ospf6_vertex
*c
;
745 /* "prefix" is the space prefix of the display line */
746 vty_out (vty
, "%s+-%s [%d]%s", prefix
, v
->name
, v
->cost
, VNL
);
748 len
= strlen (prefix
) + 4;
749 next_prefix
= (char *) malloc (len
);
750 if (next_prefix
== NULL
)
752 vty_out (vty
, "malloc failed%s", VNL
);
755 snprintf (next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
757 restnum
= listcount (v
->child_list
);
758 for (ALL_LIST_ELEMENTS (v
->child_list
, node
, nnode
, c
))
761 ospf6_spf_display_subtree (vty
, next_prefix
, restnum
, c
);
767 DEFUN (debug_ospf6_spf_process
,
768 debug_ospf6_spf_process_cmd
,
769 "debug ospf6 spf process",
772 "Debug SPF Calculation\n"
773 "Debug Detailed SPF Process\n"
776 unsigned char level
= 0;
777 level
= OSPF6_DEBUG_SPF_PROCESS
;
778 OSPF6_DEBUG_SPF_ON (level
);
782 DEFUN (debug_ospf6_spf_time
,
783 debug_ospf6_spf_time_cmd
,
784 "debug ospf6 spf time",
787 "Debug SPF Calculation\n"
788 "Measure time taken by SPF Calculation\n"
791 unsigned char level
= 0;
792 level
= OSPF6_DEBUG_SPF_TIME
;
793 OSPF6_DEBUG_SPF_ON (level
);
797 DEFUN (debug_ospf6_spf_database
,
798 debug_ospf6_spf_database_cmd
,
799 "debug ospf6 spf database",
802 "Debug SPF Calculation\n"
803 "Log number of LSAs at SPF Calculation time\n"
806 unsigned char level
= 0;
807 level
= OSPF6_DEBUG_SPF_DATABASE
;
808 OSPF6_DEBUG_SPF_ON (level
);
812 DEFUN (no_debug_ospf6_spf_process
,
813 no_debug_ospf6_spf_process_cmd
,
814 "no debug ospf6 spf process",
818 "Quit Debugging SPF Calculation\n"
819 "Quit Debugging Detailed SPF Process\n"
822 unsigned char level
= 0;
823 level
= OSPF6_DEBUG_SPF_PROCESS
;
824 OSPF6_DEBUG_SPF_OFF (level
);
828 DEFUN (no_debug_ospf6_spf_time
,
829 no_debug_ospf6_spf_time_cmd
,
830 "no debug ospf6 spf time",
834 "Quit Debugging SPF Calculation\n"
835 "Quit Measuring time taken by SPF Calculation\n"
838 unsigned char level
= 0;
839 level
= OSPF6_DEBUG_SPF_TIME
;
840 OSPF6_DEBUG_SPF_OFF (level
);
844 DEFUN (no_debug_ospf6_spf_database
,
845 no_debug_ospf6_spf_database_cmd
,
846 "no debug ospf6 spf database",
850 "Debug SPF Calculation\n"
851 "Quit Logging number of LSAs at SPF Calculation time\n"
854 unsigned char level
= 0;
855 level
= OSPF6_DEBUG_SPF_DATABASE
;
856 OSPF6_DEBUG_SPF_OFF (level
);
861 ospf6_timers_spf_set (struct vty
*vty
, unsigned int delay
,
865 VTY_DECLVAR_CONTEXT(ospf6
, ospf
);
867 ospf
->spf_delay
= delay
;
868 ospf
->spf_holdtime
= hold
;
869 ospf
->spf_max_holdtime
= max
;
874 DEFUN (ospf6_timers_throttle_spf
,
875 ospf6_timers_throttle_spf_cmd
,
876 "timers throttle spf (0-600000) (0-600000) (0-600000)",
877 "Adjust routing timers\n"
878 "Throttling adaptive timer\n"
880 "Delay (msec) from first change received till SPF calculation\n"
881 "Initial hold time (msec) between consecutive SPF calculations\n"
882 "Maximum hold time (msec)\n")
885 int idx_number_2
= 4;
886 int idx_number_3
= 5;
887 unsigned int delay
, hold
, max
;
889 VTY_GET_INTEGER_RANGE ("SPF delay timer", delay
, argv
[idx_number
]->arg
, 0, 600000);
890 VTY_GET_INTEGER_RANGE ("SPF hold timer", hold
, argv
[idx_number_2
]->arg
, 0, 600000);
891 VTY_GET_INTEGER_RANGE ("SPF max-hold timer", max
, argv
[idx_number_3
]->arg
, 0, 600000);
893 return ospf6_timers_spf_set (vty
, delay
, hold
, max
);
896 DEFUN (no_ospf6_timers_throttle_spf
,
897 no_ospf6_timers_throttle_spf_cmd
,
898 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
900 "Adjust routing timers\n"
901 "Throttling adaptive timer\n"
903 "Delay (msec) from first change received till SPF calculation\n"
904 "Initial hold time (msec) between consecutive SPF calculations\n"
905 "Maximum hold time (msec)\n")
907 return ospf6_timers_spf_set (vty
,
908 OSPF_SPF_DELAY_DEFAULT
,
909 OSPF_SPF_HOLDTIME_DEFAULT
,
910 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
915 config_write_ospf6_debug_spf (struct vty
*vty
)
917 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
918 vty_out (vty
, "debug ospf6 spf process%s", VNL
);
919 if (IS_OSPF6_DEBUG_SPF (TIME
))
920 vty_out (vty
, "debug ospf6 spf time%s", VNL
);
921 if (IS_OSPF6_DEBUG_SPF (DATABASE
))
922 vty_out (vty
, "debug ospf6 spf database%s", VNL
);
927 ospf6_spf_config_write (struct vty
*vty
)
930 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
||
931 ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
||
932 ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
933 vty_out (vty
, " timers throttle spf %d %d %d%s",
934 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
935 ospf6
->spf_max_holdtime
, VTY_NEWLINE
);
940 install_element_ospf6_debug_spf (void)
942 install_element (ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
943 install_element (ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
944 install_element (ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
945 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
946 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
947 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
948 install_element (CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
949 install_element (CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
950 install_element (CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
951 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
952 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
953 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
957 ospf6_spf_init (void)
959 install_element (OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
960 install_element (OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);