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
)
135 ntohs(lsa
->header
->type
), lsa
->name
);
141 /* capability bits + options */
142 v
->capability
= *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa
->header
));
143 v
->options
[0] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa
->header
) + 1);
144 v
->options
[1] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa
->header
) + 2);
145 v
->options
[2] = *(uint8_t *)(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 uint32_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
;
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
));
339 " another path found to route %s lsa %s, merge",
342 ospf6_spf_merge_nexthops_to_route(route
, v
);
344 prev
= (struct ospf6_vertex
*)route
->route_option
;
345 assert(prev
->hops
<= v
->hops
);
347 if ((VERTEX_IS_TYPE(ROUTER
, v
)
348 && route
->path
.origin
.id
!= v
->lsa
->header
->id
)) {
349 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
351 "%s: V lsa %s id %u, route id %u are different",
352 __PRETTY_FUNCTION__
, v
->lsa
->name
,
353 ntohl(v
->lsa
->header
->id
),
354 ntohl(route
->path
.origin
.id
));
359 ospf6_vertex_delete(v
);
363 /* There should be no case where candidate being installed (variable
364 "v") is closer than the one in the SPF tree (variable "route").
365 In the case something has gone wrong with the behavior of
368 /* the case where the route exists already is handled and returned
370 assert(route
== NULL
);
372 route
= ospf6_route_create();
373 memcpy(&route
->prefix
, &v
->vertex_id
, sizeof(struct prefix
));
374 route
->type
= OSPF6_DEST_TYPE_LINKSTATE
;
375 route
->path
.type
= OSPF6_PATH_TYPE_INTRA
;
376 route
->path
.origin
.type
= v
->lsa
->header
->type
;
377 route
->path
.origin
.id
= v
->lsa
->header
->id
;
378 route
->path
.origin
.adv_router
= v
->lsa
->header
->adv_router
;
379 route
->path
.metric_type
= 1;
380 route
->path
.cost
= v
->cost
;
381 route
->path
.u
.cost_e2
= v
->hops
;
382 route
->path
.router_bits
= v
->capability
;
383 route
->path
.options
[0] = v
->options
[0];
384 route
->path
.options
[1] = v
->options
[1];
385 route
->path
.options
[2] = v
->options
[2];
387 ospf6_spf_copy_nexthops_to_route(route
, v
);
390 * The SPF logic implementation does not transfer the multipathing
392 * of a parent to a child node. Thus if there was a 3-way multipath to a
393 * node's parent and a single hop from the parent to the child, the
395 * creating new vertices and computing next hops prevents there from
397 * paths to the child node. This is primarily because the resolution of
398 * multipath is done in this routine, not in the main spf loop.
400 * The following logic addresses that problem by merging the parent's
402 * information with the child's, if the parent is not the root of the
404 * This is based on the assumption that before a node's route is
406 * its parent's route's nexthops have already been installed.
408 if (v
->parent
&& v
->parent
->hops
) {
410 ospf6_route_lookup(&v
->parent
->vertex_id
, result_table
);
412 ospf6_route_merge_nexthops(route
, parent_route
);
417 listnode_add_sort(v
->parent
->child_list
, v
);
418 route
->route_option
= v
;
420 ospf6_route_add(route
, result_table
);
424 void ospf6_spf_table_finish(struct ospf6_route_table
*result_table
)
426 struct ospf6_route
*route
, *nroute
;
427 struct ospf6_vertex
*v
;
428 for (route
= ospf6_route_head(result_table
); route
; route
= nroute
) {
429 nroute
= ospf6_route_next(route
);
430 v
= (struct ospf6_vertex
*)route
->route_option
;
431 ospf6_vertex_delete(v
);
432 ospf6_route_remove(route
, result_table
);
436 static const char *ospf6_spf_reason_str
[] = {
437 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
440 void ospf6_spf_reason_string(unsigned int reason
, char *buf
, int size
)
448 for (bit
= 0; bit
< array_size(ospf6_spf_reason_str
); bit
++) {
449 if ((reason
& (1 << bit
)) && (len
< size
)) {
450 len
+= snprintf((buf
+ len
), (size
- len
), "%s%s",
451 (len
> 0) ? ", " : "",
452 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 */
459 void ospf6_spf_calculation(uint32_t router_id
,
460 struct ospf6_route_table
*result_table
,
461 struct ospf6_area
*oa
)
463 struct pqueue
*candidate_list
;
464 struct ospf6_vertex
*root
, *v
, *w
;
467 struct ospf6_lsa
*lsa
;
468 struct in6_addr address
;
470 ospf6_spf_table_finish(result_table
);
472 /* Install the calculating router itself as the root of the SPF tree */
473 /* construct root vertex */
474 lsa
= ospf6_create_single_router_lsa(oa
, oa
->lsdb_self
, router_id
);
476 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
477 zlog_debug("%s: No router LSA for area %s\n", __func__
,
483 candidate_list
= pqueue_create();
484 candidate_list
->cmp
= ospf6_vertex_cmp
;
486 root
= ospf6_vertex_create(lsa
);
490 root
->link_id
= lsa
->header
->id
;
491 inet_pton(AF_INET6
, "::1", &address
);
493 /* Actually insert root to the candidate-list as the only candidate */
494 pqueue_enqueue(root
, candidate_list
);
496 /* Iterate until candidate-list becomes empty */
497 while (candidate_list
->size
) {
498 /* get closest candidate from priority queue */
499 v
= pqueue_dequeue(candidate_list
);
501 /* installing may result in merging or rejecting of the vertex
503 if (ospf6_spf_install(v
, result_table
) < 0)
506 /* Skip overloaded routers */
507 if ((OSPF6_LSA_IS_TYPE(ROUTER
, v
->lsa
)
508 && ospf6_router_is_stub_router(v
->lsa
)))
511 /* For each LS description in the just-added vertex V's LSA */
512 size
= (VERTEX_IS_TYPE(ROUTER
, v
)
513 ? sizeof(struct ospf6_router_lsdesc
)
514 : sizeof(struct ospf6_network_lsdesc
));
515 for (lsdesc
= OSPF6_LSA_HEADER_END(v
->lsa
->header
) + 4;
516 lsdesc
+ size
<= OSPF6_LSA_END(v
->lsa
->header
);
518 lsa
= ospf6_lsdesc_lsa(lsdesc
, v
);
522 if (OSPF6_LSA_IS_MAXAGE(lsa
))
525 if (!ospf6_lsdesc_backlink(lsa
, lsdesc
, v
))
528 w
= ospf6_vertex_create(lsa
);
531 if (VERTEX_IS_TYPE(ROUTER
, v
)) {
533 + ROUTER_LSDESC_GET_METRIC(lsdesc
);
536 + (VERTEX_IS_TYPE(NETWORK
, w
) ? 0 : 1);
540 w
->hops
= v
->hops
+ 1;
543 /* nexthop calculation */
547 ROUTER_LSDESC_GET_IFID(lsdesc
), NULL
);
548 else if (w
->hops
== 1 && v
->hops
== 0)
549 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
))
557 " New candidate: %s hops %d cost %d",
558 w
->name
, w
->hops
, w
->cost
);
559 pqueue_enqueue(w
, candidate_list
);
564 pqueue_delete(candidate_list
);
566 ospf6_remove_temp_router_lsa(oa
);
568 oa
->spf_calculation
++;
571 static void ospf6_spf_log_database(struct ospf6_area
*oa
)
573 char *p
, *end
, buffer
[256];
574 struct listnode
*node
;
575 struct ospf6_interface
*oi
;
578 end
= buffer
+ sizeof(buffer
);
580 snprintf(p
, end
- p
, "SPF on DB (#LSAs):");
581 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
582 snprintf(p
, end
- p
, " Area %s: %d", oa
->name
, oa
->lsdb
->count
);
583 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
585 for (ALL_LIST_ELEMENTS_RO(oa
->if_list
, node
, oi
)) {
586 snprintf(p
, end
- p
, " I/F %s: %d", oi
->interface
->name
,
588 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
)
592 zlog_debug("%s", buffer
);
595 static int ospf6_spf_calculation_thread(struct thread
*t
)
597 struct ospf6_area
*oa
;
599 struct timeval start
, end
, runtime
;
600 struct listnode
*node
;
601 int areas_processed
= 0;
604 ospf6
= (struct ospf6
*)THREAD_ARG(t
);
605 ospf6
->t_spf_calc
= NULL
;
607 /* execute SPF calculation */
609 ospf6
->ts_spf
= start
;
611 if (ospf6_is_router_abr(ospf6
))
612 ospf6_abr_range_reset_cost(ospf6
);
614 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, node
, oa
)) {
616 if (oa
== ospf6
->backbone
)
619 monotime(&oa
->ts_spf
);
620 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
621 zlog_debug("SPF calculation for Area %s", oa
->name
);
622 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
623 ospf6_spf_log_database(oa
);
625 ospf6_spf_calculation(ospf6
->router_id
, oa
->spf_table
, oa
);
626 ospf6_intra_route_calculation(oa
);
627 ospf6_intra_brouter_calculation(oa
);
632 if (ospf6
->backbone
) {
633 monotime(&ospf6
->backbone
->ts_spf
);
634 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
635 zlog_debug("SPF calculation for Backbone area %s",
636 ospf6
->backbone
->name
);
637 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
638 ospf6_spf_log_database(ospf6
->backbone
);
640 ospf6_spf_calculation(ospf6
->router_id
,
641 ospf6
->backbone
->spf_table
,
643 ospf6_intra_route_calculation(ospf6
->backbone
);
644 ospf6_intra_brouter_calculation(ospf6
->backbone
);
648 if (ospf6_is_router_abr(ospf6
))
649 ospf6_abr_defaults_to_stub(ospf6
);
652 timersub(&end
, &start
, &runtime
);
654 ospf6
->ts_spf_duration
= runtime
;
656 ospf6_spf_reason_string(ospf6
->spf_reason
, rbuf
, sizeof(rbuf
));
658 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
659 zlog_debug("SPF runtime: %lld sec %lld usec",
660 (long long)runtime
.tv_sec
,
661 (long long)runtime
.tv_usec
);
664 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
666 areas_processed
, (long long)runtime
.tv_sec
,
667 (long long)runtime
.tv_usec
, rbuf
);
669 ospf6
->last_spf_reason
= ospf6
->spf_reason
;
670 ospf6_reset_spf_reason(ospf6
);
674 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
675 set timer for SPF calc. */
676 void ospf6_spf_schedule(struct ospf6
*ospf6
, unsigned int reason
)
678 unsigned long delay
, elapsed
, ht
;
680 /* OSPF instance does not exist. */
684 ospf6_set_spf_reason(ospf6
, reason
);
686 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
)) {
688 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
689 zlog_debug("SPF: calculation timer scheduled (reason %s)",
693 /* SPF calculation timer is already scheduled. */
694 if (ospf6
->t_spf_calc
) {
695 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
697 "SPF: calculation timer is already scheduled: %p",
698 (void *)ospf6
->t_spf_calc
);
702 elapsed
= monotime_since(&ospf6
->ts_spf
, NULL
) / 1000LL;
703 ht
= ospf6
->spf_holdtime
* ospf6
->spf_hold_multiplier
;
705 if (ht
> ospf6
->spf_max_holdtime
)
706 ht
= ospf6
->spf_max_holdtime
;
708 /* 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
;
723 /* Event is past required hold-time of last SPF */
724 delay
= ospf6
->spf_delay
;
725 ospf6
->spf_hold_multiplier
= 1;
728 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
729 zlog_debug("SPF: calculation timer delay = %ld", delay
);
731 zlog_info("SPF: Scheduled in %ld msec", delay
);
733 ospf6
->t_spf_calc
= NULL
;
734 thread_add_timer_msec(master
, ospf6_spf_calculation_thread
, ospf6
,
735 delay
, &ospf6
->t_spf_calc
);
738 void ospf6_spf_display_subtree(struct vty
*vty
, const char *prefix
, int rest
,
739 struct ospf6_vertex
*v
)
741 struct listnode
*node
, *nnode
;
742 struct ospf6_vertex
*c
;
747 /* "prefix" is the space prefix of the display line */
748 vty_out(vty
, "%s+-%s [%d]\n", prefix
, v
->name
, v
->cost
);
750 len
= strlen(prefix
) + 4;
751 next_prefix
= (char *)malloc(len
);
752 if (next_prefix
== NULL
) {
753 vty_out(vty
, "malloc failed\n");
756 snprintf(next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
758 restnum
= listcount(v
->child_list
);
759 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
);
860 static int ospf6_timers_spf_set(struct vty
*vty
, unsigned int delay
,
861 unsigned int hold
, unsigned int max
)
863 VTY_DECLVAR_CONTEXT(ospf6
, ospf
);
865 ospf
->spf_delay
= delay
;
866 ospf
->spf_holdtime
= hold
;
867 ospf
->spf_max_holdtime
= max
;
872 DEFUN (ospf6_timers_throttle_spf
,
873 ospf6_timers_throttle_spf_cmd
,
874 "timers throttle spf (0-600000) (0-600000) (0-600000)",
875 "Adjust routing timers\n"
876 "Throttling adaptive timer\n"
878 "Delay (msec) from first change received till SPF calculation\n"
879 "Initial hold time (msec) between consecutive SPF calculations\n"
880 "Maximum hold time (msec)\n")
883 int idx_number_2
= 4;
884 int idx_number_3
= 5;
885 unsigned int delay
, hold
, max
;
887 delay
= strtoul(argv
[idx_number
]->arg
, NULL
, 10);
888 hold
= strtoul(argv
[idx_number_2
]->arg
, NULL
, 10);
889 max
= strtoul(argv
[idx_number_3
]->arg
, NULL
, 10);
891 return ospf6_timers_spf_set(vty
, delay
, hold
, max
);
894 DEFUN (no_ospf6_timers_throttle_spf
,
895 no_ospf6_timers_throttle_spf_cmd
,
896 "no timers throttle spf [(0-600000) (0-600000) (0-600000)]",
898 "Adjust routing timers\n"
899 "Throttling adaptive timer\n"
901 "Delay (msec) from first change received till SPF calculation\n"
902 "Initial hold time (msec) between consecutive SPF calculations\n"
903 "Maximum hold time (msec)\n")
905 return ospf6_timers_spf_set(vty
, OSPF_SPF_DELAY_DEFAULT
,
906 OSPF_SPF_HOLDTIME_DEFAULT
,
907 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
911 int config_write_ospf6_debug_spf(struct vty
*vty
)
913 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
914 vty_out(vty
, "debug ospf6 spf process\n");
915 if (IS_OSPF6_DEBUG_SPF(TIME
))
916 vty_out(vty
, "debug ospf6 spf time\n");
917 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
918 vty_out(vty
, "debug ospf6 spf database\n");
922 void ospf6_spf_config_write(struct vty
*vty
)
925 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
926 || ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
927 || ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
928 vty_out(vty
, " timers throttle spf %d %d %d\n",
929 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
930 ospf6
->spf_max_holdtime
);
933 void install_element_ospf6_debug_spf(void)
935 install_element(ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
936 install_element(ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
937 install_element(ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
938 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
939 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
940 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
941 install_element(CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
942 install_element(CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
943 install_element(CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
944 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
945 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
946 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
949 void ospf6_spf_init(void)
951 install_element(OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
952 install_element(OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);
955 /* Create Aggregated Large Router-LSA from multiple Link-State IDs
957 * When more than one router-LSA is received from a single router,
958 * the links are processed as if concatenated into a single LSA.*/
959 struct ospf6_lsa
*ospf6_create_single_router_lsa(struct ospf6_area
*area
,
960 struct ospf6_lsdb
*lsdb
,
963 struct ospf6_lsa
*lsa
= NULL
;
964 struct ospf6_lsa
*rtr_lsa
= NULL
;
965 struct ospf6_lsa_header
*lsa_header
= NULL
;
966 uint8_t *new_header
= NULL
;
967 const struct route_node
*end
= NULL
;
968 uint16_t lsa_length
, total_lsa_length
= 0, num_lsa
= 0;
971 uint32_t interface_id
;
974 lsa_length
= sizeof(struct ospf6_lsa_header
)
975 + sizeof(struct ospf6_router_lsa
);
976 total_lsa_length
= lsa_length
;
977 type
= htons(OSPF6_LSTYPE_ROUTER
);
979 /* First check Aggregated LSA formed earlier in Cache */
980 lsa
= ospf6_lsdb_lookup(type
, htonl(0), adv_router
,
981 area
->temp_router_lsa_lsdb
);
985 inet_ntop(AF_INET
, &adv_router
, ifbuf
, sizeof(ifbuf
));
987 /* Determine total LSA length from all link state ids */
988 end
= ospf6_lsdb_head(lsdb
, 2, type
, adv_router
, &rtr_lsa
);
991 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
992 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
995 lsa_header
= (struct ospf6_lsa_header
*)rtr_lsa
->header
;
996 total_lsa_length
+= (ntohs(lsa_header
->length
) - lsa_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
);
1016 /* LSA information structure */
1017 lsa
= (struct ospf6_lsa
*)XCALLOC(MTYPE_OSPF6_LSA
,
1018 sizeof(struct ospf6_lsa
));
1020 lsa
->header
= (struct ospf6_lsa_header
*)new_header
;
1022 lsa
->lsdb
= area
->temp_router_lsa_lsdb
;
1024 /* Fill Larger LSA Payload */
1025 end
= ospf6_lsdb_head(lsdb
, 2, type
, adv_router
, &rtr_lsa
);
1028 * We assume at this point in time that rtr_lsa is
1032 if (!OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
1033 /* Append first Link State ID LSA */
1034 lsa_header
= (struct ospf6_lsa_header
*)rtr_lsa
->header
;
1035 memcpy(new_header
, lsa_header
, ntohs(lsa_header
->length
));
1036 /* Assign new lsa length as aggregated length. */
1037 ((struct ospf6_lsa_header
*)new_header
)->length
=
1038 htons(total_lsa_length
);
1039 new_header
+= ntohs(lsa_header
->length
);
1043 /* Print LSA Name */
1044 ospf6_lsa_printbuf(lsa
, lsa
->name
, sizeof(lsa
->name
));
1046 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1048 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
1049 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1053 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
1054 lsd
= OSPF6_LSA_HEADER_END(rtr_lsa
->header
) + 4;
1055 interface_id
= ROUTER_LSDESC_GET_IFID(lsd
);
1056 inet_ntop(AF_INET
, &interface_id
, ifbuf
, sizeof(ifbuf
));
1058 "%s: Next Router LSA %s to aggreat with len %u interface_id %s",
1059 __PRETTY_FUNCTION__
, rtr_lsa
->name
,
1060 ntohs(lsa_header
->length
), ifbuf
);
1063 /* Append Next Link State ID LSA */
1064 lsa_header
= (struct ospf6_lsa_header
*)rtr_lsa
->header
;
1065 memcpy(new_header
, (OSPF6_LSA_HEADER_END(rtr_lsa
->header
) + 4),
1066 (ntohs(lsa_header
->length
) - lsa_length
));
1067 new_header
+= (ntohs(lsa_header
->length
) - lsa_length
);
1070 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1073 /* Calculate birth of this lsa */
1074 ospf6_lsa_age_set(lsa
);
1076 /* Store Aggregated LSA into area temp lsdb */
1077 ospf6_lsdb_add(lsa
, area
->temp_router_lsa_lsdb
);
1079 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1080 zlog_debug("%s: LSA %s id %u type 0%x len %u num_lsa %u",
1081 __PRETTY_FUNCTION__
, lsa
->name
,
1082 ntohl(lsa
->header
->id
), ntohs(lsa
->header
->type
),
1083 ntohs(lsa
->header
->length
), num_lsa
);
1088 void ospf6_remove_temp_router_lsa(struct ospf6_area
*area
)
1090 struct ospf6_lsa
*lsa
= NULL
;
1092 for (ALL_LSDB(area
->temp_router_lsa_lsdb
, lsa
)) {
1093 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1095 "%s Remove LSA %s lsa->lock %u lsdb count %u",
1096 __PRETTY_FUNCTION__
, lsa
->name
, lsa
->lock
,
1097 area
->temp_router_lsa_lsdb
->count
);
1098 ospf6_lsdb_remove(lsa
, area
->temp_router_lsa_lsdb
);