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 */
606 quagga_gettime (QUAGGA_CLK_MONOTONIC
, &start
);
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
);
647 quagga_gettime (QUAGGA_CLK_MONOTONIC
, &end
);
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
;
673 struct timeval now
, result
;
675 ospf6_set_spf_reason(ospf6
, reason
);
677 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
680 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
681 zlog_debug ("SPF: calculation timer scheduled (reason %s)", rbuf
);
684 /* OSPF instance does not exist. */
688 /* SPF calculation timer is already scheduled. */
689 if (ospf6
->t_spf_calc
)
691 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
692 zlog_debug ("SPF: calculation timer is already scheduled: %p",
693 (void *)ospf6
->t_spf_calc
);
697 /* XXX Monotic timers: we only care about relative time here. */
698 now
= recent_relative_time ();
699 timersub (&now
, &ospf6
->ts_spf
, &result
);
701 elapsed
= (result
.tv_sec
* 1000) + (result
.tv_usec
/ 1000);
702 ht
= ospf6
->spf_holdtime
* ospf6
->spf_hold_multiplier
;
704 if (ht
> ospf6
->spf_max_holdtime
)
705 ht
= ospf6
->spf_max_holdtime
;
707 /* Get SPF calculation delay time. */
710 /* Got an event within the hold time of last SPF. We need to
711 * increase the hold_multiplier, if it's not already at/past
712 * maximum value, and wasn't already increased..
714 if (ht
< ospf6
->spf_max_holdtime
)
715 ospf6
->spf_hold_multiplier
++;
717 /* always honour the SPF initial delay */
718 if ( (ht
- elapsed
) < ospf6
->spf_delay
)
719 delay
= ospf6
->spf_delay
;
721 delay
= ht
- elapsed
;
725 /* Event is past required hold-time of last SPF */
726 delay
= ospf6
->spf_delay
;
727 ospf6
->spf_hold_multiplier
= 1;
730 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF (TIME
))
731 zlog_debug ("SPF: calculation timer delay = %ld", delay
);
733 zlog_info ("SPF: Scheduled in %ld msec", delay
);
736 thread_add_timer_msec (master
, ospf6_spf_calculation_thread
, ospf6
, delay
);
740 ospf6_spf_display_subtree (struct vty
*vty
, const char *prefix
, int rest
,
741 struct ospf6_vertex
*v
)
743 struct listnode
*node
, *nnode
;
744 struct ospf6_vertex
*c
;
749 /* "prefix" is the space prefix of the display line */
750 vty_out (vty
, "%s+-%s [%d]%s", prefix
, v
->name
, v
->cost
, VNL
);
752 len
= strlen (prefix
) + 4;
753 next_prefix
= (char *) malloc (len
);
754 if (next_prefix
== NULL
)
756 vty_out (vty
, "malloc failed%s", VNL
);
759 snprintf (next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
761 restnum
= listcount (v
->child_list
);
762 for (ALL_LIST_ELEMENTS (v
->child_list
, node
, nnode
, c
))
765 ospf6_spf_display_subtree (vty
, next_prefix
, restnum
, c
);
771 DEFUN (debug_ospf6_spf_process
,
772 debug_ospf6_spf_process_cmd
,
773 "debug ospf6 spf process",
776 "Debug SPF Calculation\n"
777 "Debug Detailed SPF Process\n"
780 unsigned char level
= 0;
781 level
= OSPF6_DEBUG_SPF_PROCESS
;
782 OSPF6_DEBUG_SPF_ON (level
);
786 DEFUN (debug_ospf6_spf_time
,
787 debug_ospf6_spf_time_cmd
,
788 "debug ospf6 spf time",
791 "Debug SPF Calculation\n"
792 "Measure time taken by SPF Calculation\n"
795 unsigned char level
= 0;
796 level
= OSPF6_DEBUG_SPF_TIME
;
797 OSPF6_DEBUG_SPF_ON (level
);
801 DEFUN (debug_ospf6_spf_database
,
802 debug_ospf6_spf_database_cmd
,
803 "debug ospf6 spf database",
806 "Debug SPF Calculation\n"
807 "Log number of LSAs at SPF Calculation time\n"
810 unsigned char level
= 0;
811 level
= OSPF6_DEBUG_SPF_DATABASE
;
812 OSPF6_DEBUG_SPF_ON (level
);
816 DEFUN (no_debug_ospf6_spf_process
,
817 no_debug_ospf6_spf_process_cmd
,
818 "no debug ospf6 spf process",
822 "Quit Debugging SPF Calculation\n"
823 "Quit Debugging Detailed SPF Process\n"
826 unsigned char level
= 0;
827 level
= OSPF6_DEBUG_SPF_PROCESS
;
828 OSPF6_DEBUG_SPF_OFF (level
);
832 DEFUN (no_debug_ospf6_spf_time
,
833 no_debug_ospf6_spf_time_cmd
,
834 "no debug ospf6 spf time",
838 "Quit Debugging SPF Calculation\n"
839 "Quit Measuring time taken by SPF Calculation\n"
842 unsigned char level
= 0;
843 level
= OSPF6_DEBUG_SPF_TIME
;
844 OSPF6_DEBUG_SPF_OFF (level
);
848 DEFUN (no_debug_ospf6_spf_database
,
849 no_debug_ospf6_spf_database_cmd
,
850 "no debug ospf6 spf database",
854 "Debug SPF Calculation\n"
855 "Quit Logging number of LSAs at SPF Calculation time\n"
858 unsigned char level
= 0;
859 level
= OSPF6_DEBUG_SPF_DATABASE
;
860 OSPF6_DEBUG_SPF_OFF (level
);
865 ospf6_timers_spf_set (struct vty
*vty
, unsigned int delay
,
869 struct ospf6
*ospf
= vty
->index
;
871 ospf
->spf_delay
= delay
;
872 ospf
->spf_holdtime
= hold
;
873 ospf
->spf_max_holdtime
= max
;
878 DEFUN (ospf6_timers_throttle_spf
,
879 ospf6_timers_throttle_spf_cmd
,
880 "timers throttle spf (0-600000) (0-600000) (0-600000)",
881 "Adjust routing timers\n"
882 "Throttling adaptive timer\n"
884 "Delay (msec) from first change received till SPF calculation\n"
885 "Initial hold time (msec) between consecutive SPF calculations\n"
886 "Maximum hold time (msec)\n")
889 int idx_number_2
= 4;
890 int idx_number_3
= 5;
891 unsigned int delay
, hold
, max
;
893 VTY_GET_INTEGER_RANGE ("SPF delay timer", delay
, argv
[idx_number
]->arg
, 0, 600000);
894 VTY_GET_INTEGER_RANGE ("SPF hold timer", hold
, argv
[idx_number_2
]->arg
, 0, 600000);
895 VTY_GET_INTEGER_RANGE ("SPF max-hold timer", max
, argv
[idx_number_3
]->arg
, 0, 600000);
897 return ospf6_timers_spf_set (vty
, delay
, hold
, max
);
900 DEFUN (no_ospf6_timers_throttle_spf
,
901 no_ospf6_timers_throttle_spf_cmd
,
902 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
904 "Adjust routing timers\n"
905 "Throttling adaptive timer\n"
907 "Delay (msec) from first change received till SPF calculation\n"
908 "Initial hold time (msec) between consecutive SPF calculations\n"
909 "Maximum hold time (msec)\n")
911 return ospf6_timers_spf_set (vty
,
912 OSPF_SPF_DELAY_DEFAULT
,
913 OSPF_SPF_HOLDTIME_DEFAULT
,
914 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
919 config_write_ospf6_debug_spf (struct vty
*vty
)
921 if (IS_OSPF6_DEBUG_SPF (PROCESS
))
922 vty_out (vty
, "debug ospf6 spf process%s", VNL
);
923 if (IS_OSPF6_DEBUG_SPF (TIME
))
924 vty_out (vty
, "debug ospf6 spf time%s", VNL
);
925 if (IS_OSPF6_DEBUG_SPF (DATABASE
))
926 vty_out (vty
, "debug ospf6 spf database%s", VNL
);
931 ospf6_spf_config_write (struct vty
*vty
)
934 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
||
935 ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
||
936 ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
937 vty_out (vty
, " timers throttle spf %d %d %d%s",
938 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
939 ospf6
->spf_max_holdtime
, VTY_NEWLINE
);
944 install_element_ospf6_debug_spf (void)
946 install_element (ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
947 install_element (ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
948 install_element (ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
949 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
950 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
951 install_element (ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
952 install_element (CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
953 install_element (CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
954 install_element (CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
955 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
956 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
957 install_element (CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
961 ospf6_spf_init (void)
963 install_element (OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
964 install_element (OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);