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 /* Router LSA use Link ID 0 as base in vertex_id */
116 ospf6_linkstate_prefix(lsa
->header
->adv_router
, htonl(0),
118 } else if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_NETWORK
) {
119 v
->type
= OSPF6_VERTEX_TYPE_NETWORK
;
121 ospf6_linkstate_prefix(lsa
->header
->adv_router
, lsa
->header
->id
,
127 ospf6_linkstate_prefix2str(&v
->vertex_id
, v
->name
, sizeof(v
->name
));
129 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
130 zlog_debug("%s: Creating vertex %s of type %s (0x%04hx) lsa %s",
132 ((ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
)
134 : "N/W"), ntohs(lsa
->header
->type
),
141 /* capability bits + options */
142 v
->capability
= *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
));
143 v
->options
[0] = *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
) + 1);
144 v
->options
[1] = *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
) + 2);
145 v
->options
[2] = *(u_char
*)(OSPF6_LSA_HEADER_END(lsa
->header
) + 3);
147 v
->nh_list
= list_new();
148 v
->nh_list
->cmp
= (int (*)(void *, void *))ospf6_nexthop_cmp
;
149 v
->nh_list
->del
= (void (*) (void *))ospf6_nexthop_delete
;
152 v
->child_list
= list_new();
153 v
->child_list
->cmp
= ospf6_vertex_id_cmp
;
158 static void ospf6_vertex_delete(struct ospf6_vertex
*v
)
160 list_delete_and_null(&v
->nh_list
);
161 list_delete_and_null(&v
->child_list
);
162 XFREE(MTYPE_OSPF6_VERTEX
, v
);
165 static struct ospf6_lsa
*ospf6_lsdesc_lsa(caddr_t lsdesc
,
166 struct ospf6_vertex
*v
)
168 struct ospf6_lsa
*lsa
= NULL
;
170 u_int32_t id
= 0, adv_router
= 0;
172 if (VERTEX_IS_TYPE(NETWORK
, v
)) {
173 type
= htons(OSPF6_LSTYPE_ROUTER
);
175 adv_router
= NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc
);
177 if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, lsdesc
)) {
178 type
= htons(OSPF6_LSTYPE_ROUTER
);
180 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
);
181 } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK
, lsdesc
)) {
182 type
= htons(OSPF6_LSTYPE_NETWORK
);
183 id
= htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc
));
184 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
);
188 if (type
== htons(OSPF6_LSTYPE_NETWORK
))
189 lsa
= ospf6_lsdb_lookup(type
, id
, adv_router
, v
->area
->lsdb
);
191 lsa
= ospf6_create_single_router_lsa(v
->area
, v
->area
->lsdb
,
193 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
194 char ibuf
[16], abuf
[16];
195 inet_ntop(AF_INET
, &id
, ibuf
, sizeof(ibuf
));
196 inet_ntop(AF_INET
, &adv_router
, abuf
, sizeof(abuf
));
198 zlog_debug(" Link to: %s len %u, V %s", lsa
->name
,
199 ntohs(lsa
->header
->length
), v
->name
);
201 zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA , V %s",
202 ospf6_lstype_name(type
), ibuf
, abuf
,
209 static char *ospf6_lsdesc_backlink(struct ospf6_lsa
*lsa
, caddr_t lsdesc
,
210 struct ospf6_vertex
*v
)
212 caddr_t backlink
, found
= NULL
;
215 size
= (OSPF6_LSA_IS_TYPE(ROUTER
, lsa
)
216 ? sizeof(struct ospf6_router_lsdesc
)
217 : sizeof(struct ospf6_network_lsdesc
));
218 for (backlink
= OSPF6_LSA_HEADER_END(lsa
->header
) + 4;
219 backlink
+ size
<= OSPF6_LSA_END(lsa
->header
); backlink
+= size
) {
220 assert(!(OSPF6_LSA_IS_TYPE(NETWORK
, lsa
)
221 && VERTEX_IS_TYPE(NETWORK
, v
)));
223 if (OSPF6_LSA_IS_TYPE(NETWORK
, lsa
)
224 && NETWORK_LSDESC_GET_NBR_ROUTERID(backlink
)
225 == v
->lsa
->header
->adv_router
)
227 else if (VERTEX_IS_TYPE(NETWORK
, v
)
228 && ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK
, backlink
)
229 && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink
)
230 == v
->lsa
->header
->adv_router
231 && ROUTER_LSDESC_GET_NBR_IFID(backlink
)
232 == ntohl(v
->lsa
->header
->id
))
235 if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, backlink
)
236 || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, lsdesc
))
238 if (ROUTER_LSDESC_GET_NBR_IFID(backlink
)
239 != ROUTER_LSDESC_GET_IFID(lsdesc
)
240 || ROUTER_LSDESC_GET_NBR_IFID(lsdesc
)
241 != ROUTER_LSDESC_GET_IFID(backlink
))
243 if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink
)
244 != v
->lsa
->header
->adv_router
245 || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
)
246 != lsa
->header
->adv_router
)
252 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
253 zlog_debug("Vertex %s Lsa %s Backlink %s", v
->name
, lsa
->name
,
254 (found
? "OK" : "FAIL"));
259 static void ospf6_nexthop_calc(struct ospf6_vertex
*w
, struct ospf6_vertex
*v
,
264 struct ospf6_interface
*oi
;
266 u_int32_t adv_router
;
267 struct ospf6_lsa
*lsa
;
268 struct ospf6_link_lsa
*link_lsa
;
271 assert(VERTEX_IS_TYPE(ROUTER
, w
));
272 ifindex
= (VERTEX_IS_TYPE(NETWORK
, v
) ? ospf6_spf_get_ifindex_from_nh(v
)
273 : ROUTER_LSDESC_GET_IFID(lsdesc
));
275 zlog_err("No nexthop ifindex at vertex %s", v
->name
);
279 oi
= ospf6_interface_lookup_by_ifindex(ifindex
);
281 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
282 zlog_debug("Can't find interface in SPF: ifindex %d",
287 type
= htons(OSPF6_LSTYPE_LINK
);
288 adv_router
= (VERTEX_IS_TYPE(NETWORK
, v
)
289 ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc
)
290 : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
));
293 for (ALL_LSDB_TYPED_ADVRTR(oi
->lsdb
, type
, adv_router
, lsa
)) {
294 if (VERTEX_IS_TYPE(ROUTER
, v
)
295 && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc
))
299 link_lsa
= (struct ospf6_link_lsa
*)OSPF6_LSA_HEADER_END(
301 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
302 inet_ntop(AF_INET6
, &link_lsa
->linklocal_addr
, buf
,
304 zlog_debug(" nexthop %s from %s", buf
, lsa
->name
);
307 ospf6_add_nexthop(w
->nh_list
, ifindex
,
308 &link_lsa
->linklocal_addr
);
312 if (i
== 0 && IS_OSPF6_DEBUG_SPF(PROCESS
))
313 zlog_debug("No nexthop for %s found", w
->name
);
316 static int ospf6_spf_install(struct ospf6_vertex
*v
,
317 struct ospf6_route_table
*result_table
)
319 struct ospf6_route
*route
, *parent_route
;
320 struct ospf6_vertex
*prev
;
321 char pbuf
[PREFIX2STR_BUFFER
];
323 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
324 zlog_debug("SPF install %s (lsa %s) hops %d cost %d", v
->name
,
325 v
->lsa
->name
, v
->hops
, v
->cost
);
327 route
= ospf6_route_lookup(&v
->vertex_id
, result_table
);
328 if (route
&& route
->path
.cost
< v
->cost
) {
329 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
331 " already installed with lower cost (%d), ignore",
333 ospf6_vertex_delete(v
);
335 } else if (route
&& route
->path
.cost
== v
->cost
) {
336 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
337 prefix2str(&route
->prefix
, pbuf
, sizeof(pbuf
));
338 zlog_debug(" another path found to route %s lsa %s, merge",
341 ospf6_spf_merge_nexthops_to_route(route
, v
);
343 prev
= (struct ospf6_vertex
*)route
->route_option
;
344 assert(prev
->hops
<= v
->hops
);
346 if ((VERTEX_IS_TYPE(ROUTER
, v
) &&
347 route
->path
.origin
.id
!= v
->lsa
->header
->id
)) {
348 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
349 zlog_debug("%s: V lsa %s id %u, route id %u are different",
350 __PRETTY_FUNCTION__
, v
->lsa
->name
,
351 ntohl(v
->lsa
->header
->id
),
352 ntohl(route
->path
.origin
.id
));
357 ospf6_vertex_delete(v
);
362 /* There should be no case where candidate being installed (variable
363 "v") is closer than the one in the SPF tree (variable "route").
364 In the case something has gone wrong with the behavior of
367 /* the case where the route exists already is handled and returned
369 assert(route
== NULL
);
371 route
= ospf6_route_create();
372 memcpy(&route
->prefix
, &v
->vertex_id
, sizeof(struct prefix
));
373 route
->type
= OSPF6_DEST_TYPE_LINKSTATE
;
374 route
->path
.type
= OSPF6_PATH_TYPE_INTRA
;
375 route
->path
.origin
.type
= v
->lsa
->header
->type
;
376 route
->path
.origin
.id
= v
->lsa
->header
->id
;
377 route
->path
.origin
.adv_router
= v
->lsa
->header
->adv_router
;
378 route
->path
.metric_type
= 1;
379 route
->path
.cost
= v
->cost
;
380 route
->path
.u
.cost_e2
= v
->hops
;
381 route
->path
.router_bits
= v
->capability
;
382 route
->path
.options
[0] = v
->options
[0];
383 route
->path
.options
[1] = v
->options
[1];
384 route
->path
.options
[2] = v
->options
[2];
386 ospf6_spf_copy_nexthops_to_route(route
, v
);
389 * The SPF logic implementation does not transfer the multipathing
391 * of a parent to a child node. Thus if there was a 3-way multipath to a
392 * node's parent and a single hop from the parent to the child, the
394 * creating new vertices and computing next hops prevents there from
396 * paths to the child node. This is primarily because the resolution of
397 * multipath is done in this routine, not in the main spf loop.
399 * The following logic addresses that problem by merging the parent's
401 * information with the child's, if the parent is not the root of the
403 * This is based on the assumption that before a node's route is
405 * its parent's route's nexthops have already been installed.
407 if (v
->parent
&& v
->parent
->hops
) {
409 ospf6_route_lookup(&v
->parent
->vertex_id
, result_table
);
411 ospf6_route_merge_nexthops(route
, parent_route
);
416 listnode_add_sort(v
->parent
->child_list
, v
);
417 route
->route_option
= v
;
419 ospf6_route_add(route
, result_table
);
423 void ospf6_spf_table_finish(struct ospf6_route_table
*result_table
)
425 struct ospf6_route
*route
, *nroute
;
426 struct ospf6_vertex
*v
;
427 for (route
= ospf6_route_head(result_table
); route
; route
= nroute
) {
428 nroute
= ospf6_route_next(route
);
429 v
= (struct ospf6_vertex
*)route
->route_option
;
430 ospf6_vertex_delete(v
);
431 ospf6_route_remove(route
, result_table
);
435 static const char *ospf6_spf_reason_str
[] = {
436 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
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
++) {
448 if ((reason
& (1 << bit
)) && (len
< size
)) {
449 len
+= snprintf((buf
+ len
), (size
- len
), "%s%s",
450 (len
> 0) ? ", " : "",
451 ospf6_spf_reason_str
[bit
]);
456 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
457 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
458 void ospf6_spf_calculation(u_int32_t router_id
,
459 struct ospf6_route_table
*result_table
,
460 struct ospf6_area
*oa
)
462 struct pqueue
*candidate_list
;
463 struct ospf6_vertex
*root
, *v
, *w
;
466 struct ospf6_lsa
*lsa
;
467 struct in6_addr address
;
469 ospf6_spf_table_finish(result_table
);
471 /* Install the calculating router itself as the root of the SPF tree */
472 /* construct root vertex */
473 lsa
= ospf6_create_single_router_lsa(oa
, oa
->lsdb_self
, router_id
);
475 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
476 zlog_debug("%s: No router LSA for area %s\n", __func__
,
482 candidate_list
= pqueue_create();
483 candidate_list
->cmp
= ospf6_vertex_cmp
;
485 root
= ospf6_vertex_create(lsa
);
489 root
->link_id
= lsa
->header
->id
;
490 inet_pton(AF_INET6
, "::1", &address
);
492 /* Actually insert root to the candidate-list as the only candidate */
493 pqueue_enqueue(root
, candidate_list
);
495 /* Iterate until candidate-list becomes empty */
496 while (candidate_list
->size
) {
497 /* get closest candidate from priority queue */
498 v
= pqueue_dequeue(candidate_list
);
500 /* installing may result in merging or rejecting of the vertex
502 if (ospf6_spf_install(v
, result_table
) < 0)
505 /* Skip overloaded routers */
506 if ((OSPF6_LSA_IS_TYPE(ROUTER
, v
->lsa
)
507 && ospf6_router_is_stub_router(v
->lsa
)))
510 /* For each LS description in the just-added vertex V's LSA */
511 size
= (VERTEX_IS_TYPE(ROUTER
, v
)
512 ? sizeof(struct ospf6_router_lsdesc
)
513 : sizeof(struct ospf6_network_lsdesc
));
514 for (lsdesc
= OSPF6_LSA_HEADER_END(v
->lsa
->header
) + 4;
515 lsdesc
+ size
<= OSPF6_LSA_END(v
->lsa
->header
);
517 lsa
= ospf6_lsdesc_lsa(lsdesc
, v
);
521 if (OSPF6_LSA_IS_MAXAGE(lsa
))
524 if (!ospf6_lsdesc_backlink(lsa
, lsdesc
, v
))
527 w
= ospf6_vertex_create(lsa
);
530 if (VERTEX_IS_TYPE(ROUTER
, v
)) {
532 + ROUTER_LSDESC_GET_METRIC(lsdesc
);
535 + (VERTEX_IS_TYPE(NETWORK
, w
) ? 0 : 1);
539 w
->hops
= v
->hops
+ 1;
542 /* nexthop calculation */
546 ROUTER_LSDESC_GET_IFID(lsdesc
), NULL
);
547 else if (w
->hops
== 1 && v
->hops
== 0)
548 ospf6_nexthop_calc(w
, v
, lsdesc
);
550 ospf6_copy_nexthops(w
->nh_list
, v
->nh_list
);
553 /* add new candidate to the candidate_list */
554 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
556 " New candidate: %s hops %d cost %d",
557 w
->name
, w
->hops
, w
->cost
);
558 pqueue_enqueue(w
, candidate_list
);
563 pqueue_delete(candidate_list
);
565 ospf6_remove_temp_router_lsa(oa
);
567 oa
->spf_calculation
++;
570 static void ospf6_spf_log_database(struct ospf6_area
*oa
)
572 char *p
, *end
, buffer
[256];
573 struct listnode
*node
;
574 struct ospf6_interface
*oi
;
577 end
= buffer
+ sizeof(buffer
);
579 snprintf(p
, end
- p
, "SPF on DB (#LSAs):");
580 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
581 snprintf(p
, end
- p
, " Area %s: %d", oa
->name
, oa
->lsdb
->count
);
582 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
584 for (ALL_LIST_ELEMENTS_RO(oa
->if_list
, node
, oi
)) {
585 snprintf(p
, end
- p
, " I/F %s: %d", oi
->interface
->name
,
587 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
)
591 zlog_debug("%s", buffer
);
594 static int ospf6_spf_calculation_thread(struct thread
*t
)
596 struct ospf6_area
*oa
;
598 struct timeval start
, end
, runtime
;
599 struct listnode
*node
;
600 int areas_processed
= 0;
603 ospf6
= (struct ospf6
*)THREAD_ARG(t
);
604 ospf6
->t_spf_calc
= NULL
;
606 /* execute SPF calculation */
608 ospf6
->ts_spf
= start
;
610 if (ospf6_is_router_abr(ospf6
))
611 ospf6_abr_range_reset_cost(ospf6
);
613 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, node
, oa
)) {
615 if (oa
== ospf6
->backbone
)
618 monotime(&oa
->ts_spf
);
619 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
620 zlog_debug("SPF calculation for Area %s", oa
->name
);
621 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
622 ospf6_spf_log_database(oa
);
624 ospf6_spf_calculation(ospf6
->router_id
, oa
->spf_table
, oa
);
625 ospf6_intra_route_calculation(oa
);
626 ospf6_intra_brouter_calculation(oa
);
631 if (ospf6
->backbone
) {
632 monotime(&ospf6
->backbone
->ts_spf
);
633 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
634 zlog_debug("SPF calculation for Backbone area %s",
635 ospf6
->backbone
->name
);
636 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
637 ospf6_spf_log_database(ospf6
->backbone
);
639 ospf6_spf_calculation(ospf6
->router_id
,
640 ospf6
->backbone
->spf_table
,
642 ospf6_intra_route_calculation(ospf6
->backbone
);
643 ospf6_intra_brouter_calculation(ospf6
->backbone
);
647 if (ospf6_is_router_abr(ospf6
))
648 ospf6_abr_defaults_to_stub(ospf6
);
651 timersub(&end
, &start
, &runtime
);
653 ospf6
->ts_spf_duration
= runtime
;
655 ospf6_spf_reason_string(ospf6
->spf_reason
, rbuf
, sizeof(rbuf
));
657 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
658 zlog_debug("SPF runtime: %lld sec %lld usec",
659 (long long)runtime
.tv_sec
,
660 (long long)runtime
.tv_usec
);
663 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
665 areas_processed
, (long long)runtime
.tv_sec
,
666 (long long)runtime
.tv_usec
, rbuf
);
668 ospf6
->last_spf_reason
= ospf6
->spf_reason
;
669 ospf6_reset_spf_reason(ospf6
);
673 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
674 set timer for SPF calc. */
675 void ospf6_spf_schedule(struct ospf6
*ospf6
, unsigned int reason
)
677 unsigned long delay
, elapsed
, ht
;
679 ospf6_set_spf_reason(ospf6
, reason
);
681 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
)) {
683 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
684 zlog_debug("SPF: calculation timer scheduled (reason %s)",
688 /* OSPF instance does not exist. */
692 /* SPF calculation timer is already scheduled. */
693 if (ospf6
->t_spf_calc
) {
694 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
696 "SPF: calculation timer is already scheduled: %p",
697 (void *)ospf6
->t_spf_calc
);
701 elapsed
= monotime_since(&ospf6
->ts_spf
, NULL
) / 1000LL;
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. */
709 /* Got an event within the hold time of last SPF. We need to
710 * increase the hold_multiplier, if it's not already at/past
711 * maximum value, and wasn't already increased..
713 if (ht
< ospf6
->spf_max_holdtime
)
714 ospf6
->spf_hold_multiplier
++;
716 /* always honour the SPF initial delay */
717 if ((ht
- elapsed
) < ospf6
->spf_delay
)
718 delay
= ospf6
->spf_delay
;
720 delay
= ht
- elapsed
;
722 /* Event is past required hold-time of last SPF */
723 delay
= ospf6
->spf_delay
;
724 ospf6
->spf_hold_multiplier
= 1;
727 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
728 zlog_debug("SPF: calculation timer delay = %ld", delay
);
730 zlog_info("SPF: Scheduled in %ld msec", delay
);
732 ospf6
->t_spf_calc
= NULL
;
733 thread_add_timer_msec(master
, ospf6_spf_calculation_thread
, ospf6
,
734 delay
, &ospf6
->t_spf_calc
);
737 void ospf6_spf_display_subtree(struct vty
*vty
, const char *prefix
, int rest
,
738 struct ospf6_vertex
*v
)
740 struct listnode
*node
, *nnode
;
741 struct ospf6_vertex
*c
;
746 /* "prefix" is the space prefix of the display line */
747 vty_out(vty
, "%s+-%s [%d]\n", prefix
, v
->name
, v
->cost
);
749 len
= strlen(prefix
) + 4;
750 next_prefix
= (char *)malloc(len
);
751 if (next_prefix
== NULL
) {
752 vty_out(vty
, "malloc failed\n");
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
)) {
760 ospf6_spf_display_subtree(vty
, next_prefix
, restnum
, c
);
766 DEFUN (debug_ospf6_spf_process
,
767 debug_ospf6_spf_process_cmd
,
768 "debug ospf6 spf process",
771 "Debug SPF Calculation\n"
772 "Debug Detailed SPF Process\n"
775 unsigned char level
= 0;
776 level
= OSPF6_DEBUG_SPF_PROCESS
;
777 OSPF6_DEBUG_SPF_ON(level
);
781 DEFUN (debug_ospf6_spf_time
,
782 debug_ospf6_spf_time_cmd
,
783 "debug ospf6 spf time",
786 "Debug SPF Calculation\n"
787 "Measure time taken by SPF Calculation\n"
790 unsigned char level
= 0;
791 level
= OSPF6_DEBUG_SPF_TIME
;
792 OSPF6_DEBUG_SPF_ON(level
);
796 DEFUN (debug_ospf6_spf_database
,
797 debug_ospf6_spf_database_cmd
,
798 "debug ospf6 spf database",
801 "Debug SPF Calculation\n"
802 "Log number of LSAs at SPF Calculation time\n"
805 unsigned char level
= 0;
806 level
= OSPF6_DEBUG_SPF_DATABASE
;
807 OSPF6_DEBUG_SPF_ON(level
);
811 DEFUN (no_debug_ospf6_spf_process
,
812 no_debug_ospf6_spf_process_cmd
,
813 "no debug ospf6 spf process",
817 "Quit Debugging SPF Calculation\n"
818 "Quit Debugging Detailed SPF Process\n"
821 unsigned char level
= 0;
822 level
= OSPF6_DEBUG_SPF_PROCESS
;
823 OSPF6_DEBUG_SPF_OFF(level
);
827 DEFUN (no_debug_ospf6_spf_time
,
828 no_debug_ospf6_spf_time_cmd
,
829 "no debug ospf6 spf time",
833 "Quit Debugging SPF Calculation\n"
834 "Quit Measuring time taken by SPF Calculation\n"
837 unsigned char level
= 0;
838 level
= OSPF6_DEBUG_SPF_TIME
;
839 OSPF6_DEBUG_SPF_OFF(level
);
843 DEFUN (no_debug_ospf6_spf_database
,
844 no_debug_ospf6_spf_database_cmd
,
845 "no debug ospf6 spf database",
849 "Debug SPF Calculation\n"
850 "Quit Logging number of LSAs at SPF Calculation time\n"
853 unsigned char level
= 0;
854 level
= OSPF6_DEBUG_SPF_DATABASE
;
855 OSPF6_DEBUG_SPF_OFF(level
);
859 static int ospf6_timers_spf_set(struct vty
*vty
, unsigned int delay
,
860 unsigned int hold
, unsigned int max
)
862 VTY_DECLVAR_CONTEXT(ospf6
, ospf
);
864 ospf
->spf_delay
= delay
;
865 ospf
->spf_holdtime
= hold
;
866 ospf
->spf_max_holdtime
= max
;
871 DEFUN (ospf6_timers_throttle_spf
,
872 ospf6_timers_throttle_spf_cmd
,
873 "timers throttle spf (0-600000) (0-600000) (0-600000)",
874 "Adjust routing timers\n"
875 "Throttling adaptive timer\n"
877 "Delay (msec) from first change received till SPF calculation\n"
878 "Initial hold time (msec) between consecutive SPF calculations\n"
879 "Maximum hold time (msec)\n")
882 int idx_number_2
= 4;
883 int idx_number_3
= 5;
884 unsigned int delay
, hold
, max
;
886 delay
= strtoul(argv
[idx_number
]->arg
, NULL
, 10);
887 hold
= strtoul(argv
[idx_number_2
]->arg
, NULL
, 10);
888 max
= strtoul(argv
[idx_number_3
]->arg
, NULL
, 10);
890 return ospf6_timers_spf_set(vty
, delay
, hold
, max
);
893 DEFUN (no_ospf6_timers_throttle_spf
,
894 no_ospf6_timers_throttle_spf_cmd
,
895 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
897 "Adjust routing timers\n"
898 "Throttling adaptive timer\n"
900 "Delay (msec) from first change received till SPF calculation\n"
901 "Initial hold time (msec) between consecutive SPF calculations\n"
902 "Maximum hold time (msec)\n")
904 return ospf6_timers_spf_set(vty
, OSPF_SPF_DELAY_DEFAULT
,
905 OSPF_SPF_HOLDTIME_DEFAULT
,
906 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
910 int config_write_ospf6_debug_spf(struct vty
*vty
)
912 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
913 vty_out(vty
, "debug ospf6 spf process\n");
914 if (IS_OSPF6_DEBUG_SPF(TIME
))
915 vty_out(vty
, "debug ospf6 spf time\n");
916 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
917 vty_out(vty
, "debug ospf6 spf database\n");
921 void ospf6_spf_config_write(struct vty
*vty
)
924 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
925 || ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
926 || ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
927 vty_out(vty
, " timers throttle spf %d %d %d\n",
928 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
929 ospf6
->spf_max_holdtime
);
932 void install_element_ospf6_debug_spf(void)
934 install_element(ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
935 install_element(ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
936 install_element(ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
937 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
938 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
939 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
940 install_element(CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
941 install_element(CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
942 install_element(CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
943 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
944 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
945 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
948 void ospf6_spf_init(void)
950 install_element(OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
951 install_element(OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);
954 /* Create Aggregated Large Router-LSA from multiple Link-State IDs
956 * When more than one router-LSA is received from a single router,
957 * the links are processed as if concatenated into a single LSA.*/
958 struct ospf6_lsa
*ospf6_create_single_router_lsa(struct ospf6_area
*area
,
959 struct ospf6_lsdb
*lsdb
,
962 struct ospf6_lsa
*lsa
= NULL
;
963 struct ospf6_lsa
*rtr_lsa
= NULL
;
964 struct ospf6_lsa_header
*lsa_header
= NULL
;
965 uint8_t *new_header
= NULL
;
966 const struct route_node
*end
= NULL
;
967 uint16_t lsa_length
, total_lsa_length
= 0, num_lsa
= 0;
970 uint32_t interface_id
;
973 lsa_length
= sizeof(struct ospf6_lsa_header
) +
974 sizeof(struct ospf6_router_lsa
);
975 total_lsa_length
= lsa_length
;
976 type
= htons(OSPF6_LSTYPE_ROUTER
);
978 /* First check Aggregated LSA formed earlier in Cache */
979 lsa
= ospf6_lsdb_lookup(type
, htonl(0), adv_router
,
980 area
->temp_router_lsa_lsdb
);
984 inet_ntop(AF_INET
, &adv_router
, ifbuf
, sizeof(ifbuf
));
986 /* Determine total LSA length from all link state ids */
987 end
= ospf6_lsdb_head(lsdb
, 2, type
, adv_router
, &rtr_lsa
);
990 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
991 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
994 lsa_header
= (struct ospf6_lsa_header
*) rtr_lsa
->header
;
995 total_lsa_length
+= (ntohs(lsa_header
->length
)
998 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1000 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1001 zlog_debug("%s: adv_router %s num_lsa %u to convert.",
1002 __PRETTY_FUNCTION__
, ifbuf
, num_lsa
);
1007 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1008 zlog_debug("%s: adv_router %s not found in LSDB.",
1009 __PRETTY_FUNCTION__
, ifbuf
);
1013 /* Allocate memory for this LSA */
1014 new_header
= XMALLOC(MTYPE_OSPF6_LSA_HEADER
, total_lsa_length
);
1018 /* LSA information structure */
1019 lsa
= (struct ospf6_lsa
*)XCALLOC(MTYPE_OSPF6_LSA
,
1020 sizeof(struct ospf6_lsa
));
1026 lsa
->header
= (struct ospf6_lsa_header
*)new_header
;
1028 lsa
->lsdb
= area
->temp_router_lsa_lsdb
;
1030 /* Fill Larger LSA Payload */
1031 end
= ospf6_lsdb_head(lsdb
, 2, type
, adv_router
, &rtr_lsa
);
1034 * We assume at this point in time that rtr_lsa is
1038 if (!OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
1039 /* Append first Link State ID LSA */
1040 lsa_header
= (struct ospf6_lsa_header
*)rtr_lsa
->header
;
1041 memcpy(new_header
, lsa_header
, ntohs(lsa_header
->length
));
1042 /* Assign new lsa length as aggregated length. */
1043 ((struct ospf6_lsa_header
*)new_header
)->length
=
1044 htons(total_lsa_length
);
1045 new_header
+= ntohs(lsa_header
->length
);
1049 /* Print LSA Name */
1050 ospf6_lsa_printbuf(lsa
, lsa
->name
, sizeof(lsa
->name
));
1052 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1054 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
1055 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1059 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
1060 lsd
= OSPF6_LSA_HEADER_END(rtr_lsa
->header
) + 4;
1061 interface_id
= ROUTER_LSDESC_GET_IFID(lsd
);
1062 inet_ntop(AF_INET
, &interface_id
, ifbuf
, sizeof(ifbuf
));
1063 zlog_debug("%s: Next Router LSA %s to aggreat with len %u interface_id %s",
1064 __PRETTY_FUNCTION__
, rtr_lsa
->name
,
1065 ntohs(lsa_header
->length
), ifbuf
);
1068 /* Append Next Link State ID LSA */
1069 lsa_header
= (struct ospf6_lsa_header
*) rtr_lsa
->header
;
1070 memcpy(new_header
, (OSPF6_LSA_HEADER_END(rtr_lsa
->header
) + 4),
1071 (ntohs(lsa_header
->length
) - lsa_length
));
1072 new_header
+= (ntohs(lsa_header
->length
) - lsa_length
);
1075 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1078 /* Calculate birth of this lsa */
1079 ospf6_lsa_age_set(lsa
);
1081 /* Store Aggregated LSA into area temp lsdb */
1082 ospf6_lsdb_add(lsa
, area
->temp_router_lsa_lsdb
);
1084 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1085 zlog_debug("%s: LSA %s id %u type 0%x len %u num_lsa %u",
1086 __PRETTY_FUNCTION__
, lsa
->name
,
1087 ntohl(lsa
->header
->id
), ntohs(lsa
->header
->type
),
1088 ntohs(lsa
->header
->length
), num_lsa
);
1093 void ospf6_remove_temp_router_lsa(struct ospf6_area
*area
)
1095 struct ospf6_lsa
*lsa
= NULL
;
1097 for (ALL_LSDB(area
->temp_router_lsa_lsdb
, lsa
)) {
1098 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1099 zlog_debug("%s Remove LSA %s lsa->lock %u lsdb count %u",
1100 __PRETTY_FUNCTION__
,
1101 lsa
->name
, lsa
->lock
,
1102 area
->temp_router_lsa_lsdb
->count
);
1103 ospf6_lsdb_remove(lsa
, area
->temp_router_lsa_lsdb
);