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 */
33 #include "lib_errors.h"
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;
49 static void ospf6_spf_copy_nexthops_to_route(struct ospf6_route
*rt
,
50 struct ospf6_vertex
*v
)
53 ospf6_copy_nexthops(rt
->nh_list
, v
->nh_list
);
56 static void ospf6_spf_merge_nexthops_to_route(struct ospf6_route
*rt
,
57 struct ospf6_vertex
*v
)
60 ospf6_merge_nexthops(rt
->nh_list
, v
->nh_list
);
63 static unsigned int ospf6_spf_get_ifindex_from_nh(struct ospf6_vertex
*v
)
65 struct ospf6_nexthop
*nh
;
66 struct listnode
*node
;
69 node
= listhead(v
->nh_list
);
71 nh
= listgetdata(node
);
79 static int ospf6_vertex_cmp(void *a
, void *b
)
81 struct ospf6_vertex
*va
= (struct ospf6_vertex
*)a
;
82 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*)b
;
85 if (va
->cost
!= vb
->cost
)
86 return (va
->cost
- vb
->cost
);
87 return (va
->hops
- vb
->hops
);
90 static int ospf6_vertex_id_cmp(void *a
, void *b
)
92 struct ospf6_vertex
*va
= (struct ospf6_vertex
*)a
;
93 struct ospf6_vertex
*vb
= (struct ospf6_vertex
*)b
;
96 ret
= ntohl(ospf6_linkstate_prefix_adv_router(&va
->vertex_id
))
97 - ntohl(ospf6_linkstate_prefix_adv_router(&vb
->vertex_id
));
101 ret
= ntohl(ospf6_linkstate_prefix_id(&va
->vertex_id
))
102 - ntohl(ospf6_linkstate_prefix_id(&vb
->vertex_id
));
106 static struct ospf6_vertex
*ospf6_vertex_create(struct ospf6_lsa
*lsa
)
108 struct ospf6_vertex
*v
;
110 v
= (struct ospf6_vertex
*)XMALLOC(MTYPE_OSPF6_VERTEX
,
111 sizeof(struct ospf6_vertex
));
114 if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
) {
115 v
->type
= OSPF6_VERTEX_TYPE_ROUTER
;
116 /* Router LSA use Link ID 0 as base in vertex_id */
117 ospf6_linkstate_prefix(lsa
->header
->adv_router
, htonl(0),
119 } else if (ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_NETWORK
) {
120 v
->type
= OSPF6_VERTEX_TYPE_NETWORK
;
122 ospf6_linkstate_prefix(lsa
->header
->adv_router
, lsa
->header
->id
,
128 ospf6_linkstate_prefix2str(&v
->vertex_id
, v
->name
, sizeof(v
->name
));
130 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
131 zlog_debug("%s: Creating vertex %s of type %s (0x%04hx) lsa %s",
133 ((ntohs(lsa
->header
->type
) == OSPF6_LSTYPE_ROUTER
)
136 ntohs(lsa
->header
->type
), lsa
->name
);
142 /* capability bits + options */
143 v
->capability
= *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa
->header
));
144 v
->options
[0] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa
->header
) + 1);
145 v
->options
[1] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa
->header
) + 2);
146 v
->options
[2] = *(uint8_t *)(OSPF6_LSA_HEADER_END(lsa
->header
) + 3);
148 v
->nh_list
= list_new();
149 v
->nh_list
->cmp
= (int (*)(void *, void *))ospf6_nexthop_cmp
;
150 v
->nh_list
->del
= (void (*)(void *))ospf6_nexthop_delete
;
153 v
->child_list
= list_new();
154 v
->child_list
->cmp
= ospf6_vertex_id_cmp
;
159 static void ospf6_vertex_delete(struct ospf6_vertex
*v
)
161 list_delete_and_null(&v
->nh_list
);
162 list_delete_and_null(&v
->child_list
);
163 XFREE(MTYPE_OSPF6_VERTEX
, v
);
166 static struct ospf6_lsa
*ospf6_lsdesc_lsa(caddr_t lsdesc
,
167 struct ospf6_vertex
*v
)
169 struct ospf6_lsa
*lsa
= NULL
;
171 uint32_t id
= 0, adv_router
= 0;
173 if (VERTEX_IS_TYPE(NETWORK
, v
)) {
174 type
= htons(OSPF6_LSTYPE_ROUTER
);
176 adv_router
= NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc
);
178 if (ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, lsdesc
)) {
179 type
= htons(OSPF6_LSTYPE_ROUTER
);
181 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
);
182 } else if (ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK
, lsdesc
)) {
183 type
= htons(OSPF6_LSTYPE_NETWORK
);
184 id
= htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc
));
185 adv_router
= ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
);
189 if (type
== htons(OSPF6_LSTYPE_NETWORK
))
190 lsa
= ospf6_lsdb_lookup(type
, id
, adv_router
, v
->area
->lsdb
);
192 lsa
= ospf6_create_single_router_lsa(v
->area
, v
->area
->lsdb
,
194 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
195 char ibuf
[16], abuf
[16];
196 inet_ntop(AF_INET
, &id
, ibuf
, sizeof(ibuf
));
197 inet_ntop(AF_INET
, &adv_router
, abuf
, sizeof(abuf
));
199 zlog_debug(" Link to: %s len %u, V %s", lsa
->name
,
200 ntohs(lsa
->header
->length
), v
->name
);
202 zlog_debug(" Link to: [%s Id:%s Adv:%s] No LSA , V %s",
203 ospf6_lstype_name(type
), ibuf
, abuf
,
210 static char *ospf6_lsdesc_backlink(struct ospf6_lsa
*lsa
, caddr_t lsdesc
,
211 struct ospf6_vertex
*v
)
213 caddr_t backlink
, found
= NULL
;
216 size
= (OSPF6_LSA_IS_TYPE(ROUTER
, lsa
)
217 ? sizeof(struct ospf6_router_lsdesc
)
218 : sizeof(struct ospf6_network_lsdesc
));
219 for (backlink
= OSPF6_LSA_HEADER_END(lsa
->header
) + 4;
220 backlink
+ size
<= OSPF6_LSA_END(lsa
->header
); backlink
+= size
) {
221 assert(!(OSPF6_LSA_IS_TYPE(NETWORK
, lsa
)
222 && VERTEX_IS_TYPE(NETWORK
, v
)));
224 if (OSPF6_LSA_IS_TYPE(NETWORK
, lsa
)
225 && NETWORK_LSDESC_GET_NBR_ROUTERID(backlink
)
226 == v
->lsa
->header
->adv_router
)
228 else if (VERTEX_IS_TYPE(NETWORK
, v
)
229 && ROUTER_LSDESC_IS_TYPE(TRANSIT_NETWORK
, backlink
)
230 && ROUTER_LSDESC_GET_NBR_ROUTERID(backlink
)
231 == v
->lsa
->header
->adv_router
232 && ROUTER_LSDESC_GET_NBR_IFID(backlink
)
233 == ntohl(v
->lsa
->header
->id
))
236 if (!ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, backlink
)
237 || !ROUTER_LSDESC_IS_TYPE(POINTTOPOINT
, lsdesc
))
239 if (ROUTER_LSDESC_GET_NBR_IFID(backlink
)
240 != ROUTER_LSDESC_GET_IFID(lsdesc
)
241 || ROUTER_LSDESC_GET_NBR_IFID(lsdesc
)
242 != ROUTER_LSDESC_GET_IFID(backlink
))
244 if (ROUTER_LSDESC_GET_NBR_ROUTERID(backlink
)
245 != v
->lsa
->header
->adv_router
246 || ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
)
247 != lsa
->header
->adv_router
)
253 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
254 zlog_debug("Vertex %s Lsa %s Backlink %s", v
->name
, lsa
->name
,
255 (found
? "OK" : "FAIL"));
260 static void ospf6_nexthop_calc(struct ospf6_vertex
*w
, struct ospf6_vertex
*v
,
265 struct ospf6_interface
*oi
;
268 struct ospf6_lsa
*lsa
;
269 struct ospf6_link_lsa
*link_lsa
;
272 assert(VERTEX_IS_TYPE(ROUTER
, w
));
273 ifindex
= (VERTEX_IS_TYPE(NETWORK
, v
) ? ospf6_spf_get_ifindex_from_nh(v
)
274 : ROUTER_LSDESC_GET_IFID(lsdesc
));
276 flog_err(LIB_ERR_DEVELOPMENT
,
277 "No nexthop ifindex at vertex %s", v
->name
);
281 oi
= ospf6_interface_lookup_by_ifindex(ifindex
);
283 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
284 zlog_debug("Can't find interface in SPF: ifindex %d",
289 type
= htons(OSPF6_LSTYPE_LINK
);
290 adv_router
= (VERTEX_IS_TYPE(NETWORK
, v
)
291 ? NETWORK_LSDESC_GET_NBR_ROUTERID(lsdesc
)
292 : ROUTER_LSDESC_GET_NBR_ROUTERID(lsdesc
));
295 for (ALL_LSDB_TYPED_ADVRTR(oi
->lsdb
, type
, adv_router
, lsa
)) {
296 if (VERTEX_IS_TYPE(ROUTER
, v
)
297 && htonl(ROUTER_LSDESC_GET_NBR_IFID(lsdesc
))
301 link_lsa
= (struct ospf6_link_lsa
*)OSPF6_LSA_HEADER_END(
303 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
304 inet_ntop(AF_INET6
, &link_lsa
->linklocal_addr
, buf
,
306 zlog_debug(" nexthop %s from %s", buf
, lsa
->name
);
309 ospf6_add_nexthop(w
->nh_list
, ifindex
,
310 &link_lsa
->linklocal_addr
);
314 if (i
== 0 && IS_OSPF6_DEBUG_SPF(PROCESS
))
315 zlog_debug("No nexthop for %s found", w
->name
);
318 static int ospf6_spf_install(struct ospf6_vertex
*v
,
319 struct ospf6_route_table
*result_table
)
321 struct ospf6_route
*route
, *parent_route
;
322 struct ospf6_vertex
*prev
;
323 char pbuf
[PREFIX2STR_BUFFER
];
325 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
326 zlog_debug("SPF install %s (lsa %s) hops %d cost %d", v
->name
,
327 v
->lsa
->name
, v
->hops
, v
->cost
);
329 route
= ospf6_route_lookup(&v
->vertex_id
, result_table
);
330 if (route
&& route
->path
.cost
< v
->cost
) {
331 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
333 " already installed with lower cost (%d), ignore",
335 ospf6_vertex_delete(v
);
337 } else if (route
&& route
->path
.cost
== v
->cost
) {
338 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
339 prefix2str(&route
->prefix
, pbuf
, sizeof(pbuf
));
341 " another path found to route %s lsa %s, merge",
344 ospf6_spf_merge_nexthops_to_route(route
, v
);
346 prev
= (struct ospf6_vertex
*)route
->route_option
;
347 assert(prev
->hops
<= v
->hops
);
349 if ((VERTEX_IS_TYPE(ROUTER
, v
)
350 && route
->path
.origin
.id
!= v
->lsa
->header
->id
)) {
351 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
353 "%s: V lsa %s id %u, route id %u are different",
354 __PRETTY_FUNCTION__
, v
->lsa
->name
,
355 ntohl(v
->lsa
->header
->id
),
356 ntohl(route
->path
.origin
.id
));
361 ospf6_vertex_delete(v
);
365 /* There should be no case where candidate being installed (variable
366 "v") is closer than the one in the SPF tree (variable "route").
367 In the case something has gone wrong with the behavior of
370 /* the case where the route exists already is handled and returned
372 assert(route
== NULL
);
374 route
= ospf6_route_create();
375 memcpy(&route
->prefix
, &v
->vertex_id
, sizeof(struct prefix
));
376 route
->type
= OSPF6_DEST_TYPE_LINKSTATE
;
377 route
->path
.type
= OSPF6_PATH_TYPE_INTRA
;
378 route
->path
.origin
.type
= v
->lsa
->header
->type
;
379 route
->path
.origin
.id
= v
->lsa
->header
->id
;
380 route
->path
.origin
.adv_router
= v
->lsa
->header
->adv_router
;
381 route
->path
.metric_type
= 1;
382 route
->path
.cost
= v
->cost
;
383 route
->path
.u
.cost_e2
= v
->hops
;
384 route
->path
.router_bits
= v
->capability
;
385 route
->path
.options
[0] = v
->options
[0];
386 route
->path
.options
[1] = v
->options
[1];
387 route
->path
.options
[2] = v
->options
[2];
389 ospf6_spf_copy_nexthops_to_route(route
, v
);
392 * The SPF logic implementation does not transfer the multipathing
394 * of a parent to a child node. Thus if there was a 3-way multipath to a
395 * node's parent and a single hop from the parent to the child, the
397 * creating new vertices and computing next hops prevents there from
399 * paths to the child node. This is primarily because the resolution of
400 * multipath is done in this routine, not in the main spf loop.
402 * The following logic addresses that problem by merging the parent's
404 * information with the child's, if the parent is not the root of the
406 * This is based on the assumption that before a node's route is
408 * its parent's route's nexthops have already been installed.
410 if (v
->parent
&& v
->parent
->hops
) {
412 ospf6_route_lookup(&v
->parent
->vertex_id
, result_table
);
414 ospf6_route_merge_nexthops(route
, parent_route
);
419 listnode_add_sort(v
->parent
->child_list
, v
);
420 route
->route_option
= v
;
422 ospf6_route_add(route
, result_table
);
426 void ospf6_spf_table_finish(struct ospf6_route_table
*result_table
)
428 struct ospf6_route
*route
, *nroute
;
429 struct ospf6_vertex
*v
;
430 for (route
= ospf6_route_head(result_table
); route
; route
= nroute
) {
431 nroute
= ospf6_route_next(route
);
432 v
= (struct ospf6_vertex
*)route
->route_option
;
433 ospf6_vertex_delete(v
);
434 ospf6_route_remove(route
, result_table
);
438 static const char *ospf6_spf_reason_str
[] = {
439 "R+", "R-", "N+", "N-", "L+", "L-", "R*", "N*",
442 void ospf6_spf_reason_string(unsigned int reason
, char *buf
, int size
)
450 for (bit
= 0; bit
< array_size(ospf6_spf_reason_str
); bit
++) {
451 if ((reason
& (1 << bit
)) && (len
< size
)) {
452 len
+= snprintf((buf
+ len
), (size
- len
), "%s%s",
453 (len
> 0) ? ", " : "",
454 ospf6_spf_reason_str
[bit
]);
459 /* RFC2328 16.1. Calculating the shortest-path tree for an area */
460 /* RFC2740 3.8.1. Calculating the shortest path tree for an area */
461 void ospf6_spf_calculation(uint32_t router_id
,
462 struct ospf6_route_table
*result_table
,
463 struct ospf6_area
*oa
)
465 struct pqueue
*candidate_list
;
466 struct ospf6_vertex
*root
, *v
, *w
;
469 struct ospf6_lsa
*lsa
;
470 struct in6_addr address
;
472 ospf6_spf_table_finish(result_table
);
474 /* Install the calculating router itself as the root of the SPF tree */
475 /* construct root vertex */
476 lsa
= ospf6_create_single_router_lsa(oa
, oa
->lsdb_self
, router_id
);
478 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
479 zlog_debug("%s: No router LSA for area %s\n", __func__
,
485 candidate_list
= pqueue_create();
486 candidate_list
->cmp
= ospf6_vertex_cmp
;
488 root
= ospf6_vertex_create(lsa
);
492 root
->link_id
= lsa
->header
->id
;
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
) {
500 /* get closest candidate from priority queue */
501 v
= pqueue_dequeue(candidate_list
);
503 /* 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
);
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 + ROUTER_LSDESC_GET_METRIC(lsdesc
);
538 + (VERTEX_IS_TYPE(NETWORK
, w
) ? 0 : 1);
542 w
->hops
= v
->hops
+ 1;
545 /* nexthop calculation */
549 ROUTER_LSDESC_GET_IFID(lsdesc
), NULL
);
550 else if (w
->hops
== 1 && v
->hops
== 0)
551 ospf6_nexthop_calc(w
, v
, lsdesc
);
553 ospf6_copy_nexthops(w
->nh_list
, v
->nh_list
);
556 /* add new candidate to the candidate_list */
557 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
559 " New candidate: %s hops %d cost %d",
560 w
->name
, w
->hops
, w
->cost
);
561 pqueue_enqueue(w
, candidate_list
);
566 pqueue_delete(candidate_list
);
568 ospf6_remove_temp_router_lsa(oa
);
570 oa
->spf_calculation
++;
573 static void ospf6_spf_log_database(struct ospf6_area
*oa
)
575 char *p
, *end
, buffer
[256];
576 struct listnode
*node
;
577 struct ospf6_interface
*oi
;
580 end
= buffer
+ sizeof(buffer
);
582 snprintf(p
, end
- p
, "SPF on DB (#LSAs):");
583 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
584 snprintf(p
, end
- p
, " Area %s: %d", oa
->name
, oa
->lsdb
->count
);
585 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
) : end
);
587 for (ALL_LIST_ELEMENTS_RO(oa
->if_list
, node
, oi
)) {
588 snprintf(p
, end
- p
, " I/F %s: %d", oi
->interface
->name
,
590 p
= (buffer
+ strlen(buffer
) < end
? buffer
+ strlen(buffer
)
594 zlog_debug("%s", buffer
);
597 static int ospf6_spf_calculation_thread(struct thread
*t
)
599 struct ospf6_area
*oa
;
601 struct timeval start
, end
, runtime
;
602 struct listnode
*node
;
603 int areas_processed
= 0;
606 ospf6
= (struct ospf6
*)THREAD_ARG(t
);
607 ospf6
->t_spf_calc
= NULL
;
609 /* execute SPF calculation */
611 ospf6
->ts_spf
= start
;
613 if (ospf6_is_router_abr(ospf6
))
614 ospf6_abr_range_reset_cost(ospf6
);
616 for (ALL_LIST_ELEMENTS_RO(ospf6
->area_list
, node
, oa
)) {
618 if (oa
== ospf6
->backbone
)
621 monotime(&oa
->ts_spf
);
622 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
623 zlog_debug("SPF calculation for Area %s", oa
->name
);
624 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
625 ospf6_spf_log_database(oa
);
627 ospf6_spf_calculation(ospf6
->router_id
, oa
->spf_table
, oa
);
628 ospf6_intra_route_calculation(oa
);
629 ospf6_intra_brouter_calculation(oa
);
634 if (ospf6
->backbone
) {
635 monotime(&ospf6
->backbone
->ts_spf
);
636 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
637 zlog_debug("SPF calculation for Backbone area %s",
638 ospf6
->backbone
->name
);
639 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
640 ospf6_spf_log_database(ospf6
->backbone
);
642 ospf6_spf_calculation(ospf6
->router_id
,
643 ospf6
->backbone
->spf_table
,
645 ospf6_intra_route_calculation(ospf6
->backbone
);
646 ospf6_intra_brouter_calculation(ospf6
->backbone
);
650 if (ospf6_is_router_abr(ospf6
))
651 ospf6_abr_defaults_to_stub(ospf6
);
654 timersub(&end
, &start
, &runtime
);
656 ospf6
->ts_spf_duration
= runtime
;
658 ospf6_spf_reason_string(ospf6
->spf_reason
, rbuf
, sizeof(rbuf
));
660 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
661 zlog_debug("SPF runtime: %lld sec %lld usec",
662 (long long)runtime
.tv_sec
,
663 (long long)runtime
.tv_usec
);
666 "SPF processing: # Areas: %d, SPF runtime: %lld sec %lld usec, "
668 areas_processed
, (long long)runtime
.tv_sec
,
669 (long long)runtime
.tv_usec
, rbuf
);
671 ospf6
->last_spf_reason
= ospf6
->spf_reason
;
672 ospf6_reset_spf_reason(ospf6
);
676 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
677 set timer for SPF calc. */
678 void ospf6_spf_schedule(struct ospf6
*ospf6
, unsigned int reason
)
680 unsigned long delay
, elapsed
, ht
;
682 /* OSPF instance does not exist. */
686 ospf6_set_spf_reason(ospf6
, reason
);
688 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
)) {
690 ospf6_spf_reason_string(reason
, rbuf
, sizeof(rbuf
));
691 zlog_debug("SPF: calculation timer scheduled (reason %s)",
695 /* SPF calculation timer is already scheduled. */
696 if (ospf6
->t_spf_calc
) {
697 if (IS_OSPF6_DEBUG_SPF(PROCESS
) || IS_OSPF6_DEBUG_SPF(TIME
))
699 "SPF: calculation timer is already scheduled: %p",
700 (void *)ospf6
->t_spf_calc
);
704 elapsed
= monotime_since(&ospf6
->ts_spf
, NULL
) / 1000LL;
705 ht
= ospf6
->spf_holdtime
* ospf6
->spf_hold_multiplier
;
707 if (ht
> ospf6
->spf_max_holdtime
)
708 ht
= ospf6
->spf_max_holdtime
;
710 /* Get SPF calculation delay time. */
712 /* Got an event within the hold time of last SPF. We need to
713 * increase the hold_multiplier, if it's not already at/past
714 * maximum value, and wasn't already increased..
716 if (ht
< ospf6
->spf_max_holdtime
)
717 ospf6
->spf_hold_multiplier
++;
719 /* always honour the SPF initial delay */
720 if ((ht
- elapsed
) < ospf6
->spf_delay
)
721 delay
= ospf6
->spf_delay
;
723 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
);
735 ospf6
->t_spf_calc
= NULL
;
736 thread_add_timer_msec(master
, ospf6_spf_calculation_thread
, ospf6
,
737 delay
, &ospf6
->t_spf_calc
);
740 void 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]\n", prefix
, v
->name
, v
->cost
);
752 len
= strlen(prefix
) + 4;
753 next_prefix
= (char *)malloc(len
);
754 if (next_prefix
== NULL
) {
755 vty_out(vty
, "malloc failed\n");
758 snprintf(next_prefix
, len
, "%s%s", prefix
, (rest
? "| " : " "));
760 restnum
= listcount(v
->child_list
);
761 for (ALL_LIST_ELEMENTS(v
->child_list
, node
, nnode
, c
)) {
763 ospf6_spf_display_subtree(vty
, next_prefix
, restnum
, c
);
769 DEFUN (debug_ospf6_spf_process
,
770 debug_ospf6_spf_process_cmd
,
771 "debug ospf6 spf process",
774 "Debug SPF Calculation\n"
775 "Debug Detailed SPF Process\n"
778 unsigned char level
= 0;
779 level
= OSPF6_DEBUG_SPF_PROCESS
;
780 OSPF6_DEBUG_SPF_ON(level
);
784 DEFUN (debug_ospf6_spf_time
,
785 debug_ospf6_spf_time_cmd
,
786 "debug ospf6 spf time",
789 "Debug SPF Calculation\n"
790 "Measure time taken by SPF Calculation\n"
793 unsigned char level
= 0;
794 level
= OSPF6_DEBUG_SPF_TIME
;
795 OSPF6_DEBUG_SPF_ON(level
);
799 DEFUN (debug_ospf6_spf_database
,
800 debug_ospf6_spf_database_cmd
,
801 "debug ospf6 spf database",
804 "Debug SPF Calculation\n"
805 "Log number of LSAs at SPF Calculation time\n"
808 unsigned char level
= 0;
809 level
= OSPF6_DEBUG_SPF_DATABASE
;
810 OSPF6_DEBUG_SPF_ON(level
);
814 DEFUN (no_debug_ospf6_spf_process
,
815 no_debug_ospf6_spf_process_cmd
,
816 "no debug ospf6 spf process",
820 "Quit Debugging SPF Calculation\n"
821 "Quit Debugging Detailed SPF Process\n"
824 unsigned char level
= 0;
825 level
= OSPF6_DEBUG_SPF_PROCESS
;
826 OSPF6_DEBUG_SPF_OFF(level
);
830 DEFUN (no_debug_ospf6_spf_time
,
831 no_debug_ospf6_spf_time_cmd
,
832 "no debug ospf6 spf time",
836 "Quit Debugging SPF Calculation\n"
837 "Quit Measuring time taken by SPF Calculation\n"
840 unsigned char level
= 0;
841 level
= OSPF6_DEBUG_SPF_TIME
;
842 OSPF6_DEBUG_SPF_OFF(level
);
846 DEFUN (no_debug_ospf6_spf_database
,
847 no_debug_ospf6_spf_database_cmd
,
848 "no debug ospf6 spf database",
852 "Debug SPF Calculation\n"
853 "Quit Logging number of LSAs at SPF Calculation time\n"
856 unsigned char level
= 0;
857 level
= OSPF6_DEBUG_SPF_DATABASE
;
858 OSPF6_DEBUG_SPF_OFF(level
);
862 static int ospf6_timers_spf_set(struct vty
*vty
, unsigned int delay
,
863 unsigned int hold
, unsigned int max
)
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 delay
= strtoul(argv
[idx_number
]->arg
, NULL
, 10);
890 hold
= strtoul(argv
[idx_number_2
]->arg
, NULL
, 10);
891 max
= strtoul(argv
[idx_number_3
]->arg
, NULL
, 10);
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
, OSPF_SPF_DELAY_DEFAULT
,
908 OSPF_SPF_HOLDTIME_DEFAULT
,
909 OSPF_SPF_MAX_HOLDTIME_DEFAULT
);
913 int config_write_ospf6_debug_spf(struct vty
*vty
)
915 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
916 vty_out(vty
, "debug ospf6 spf process\n");
917 if (IS_OSPF6_DEBUG_SPF(TIME
))
918 vty_out(vty
, "debug ospf6 spf time\n");
919 if (IS_OSPF6_DEBUG_SPF(DATABASE
))
920 vty_out(vty
, "debug ospf6 spf database\n");
924 void ospf6_spf_config_write(struct vty
*vty
)
927 if (ospf6
->spf_delay
!= OSPF_SPF_DELAY_DEFAULT
928 || ospf6
->spf_holdtime
!= OSPF_SPF_HOLDTIME_DEFAULT
929 || ospf6
->spf_max_holdtime
!= OSPF_SPF_MAX_HOLDTIME_DEFAULT
)
930 vty_out(vty
, " timers throttle spf %d %d %d\n",
931 ospf6
->spf_delay
, ospf6
->spf_holdtime
,
932 ospf6
->spf_max_holdtime
);
935 void install_element_ospf6_debug_spf(void)
937 install_element(ENABLE_NODE
, &debug_ospf6_spf_process_cmd
);
938 install_element(ENABLE_NODE
, &debug_ospf6_spf_time_cmd
);
939 install_element(ENABLE_NODE
, &debug_ospf6_spf_database_cmd
);
940 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_process_cmd
);
941 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_time_cmd
);
942 install_element(ENABLE_NODE
, &no_debug_ospf6_spf_database_cmd
);
943 install_element(CONFIG_NODE
, &debug_ospf6_spf_process_cmd
);
944 install_element(CONFIG_NODE
, &debug_ospf6_spf_time_cmd
);
945 install_element(CONFIG_NODE
, &debug_ospf6_spf_database_cmd
);
946 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_process_cmd
);
947 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_time_cmd
);
948 install_element(CONFIG_NODE
, &no_debug_ospf6_spf_database_cmd
);
951 void ospf6_spf_init(void)
953 install_element(OSPF6_NODE
, &ospf6_timers_throttle_spf_cmd
);
954 install_element(OSPF6_NODE
, &no_ospf6_timers_throttle_spf_cmd
);
957 /* Create Aggregated Large Router-LSA from multiple Link-State IDs
959 * When more than one router-LSA is received from a single router,
960 * the links are processed as if concatenated into a single LSA.*/
961 struct ospf6_lsa
*ospf6_create_single_router_lsa(struct ospf6_area
*area
,
962 struct ospf6_lsdb
*lsdb
,
965 struct ospf6_lsa
*lsa
= NULL
;
966 struct ospf6_lsa
*rtr_lsa
= NULL
;
967 struct ospf6_lsa_header
*lsa_header
= NULL
;
968 uint8_t *new_header
= NULL
;
969 const struct route_node
*end
= NULL
;
970 uint16_t lsa_length
, total_lsa_length
= 0, num_lsa
= 0;
973 uint32_t interface_id
;
976 lsa_length
= sizeof(struct ospf6_lsa_header
)
977 + sizeof(struct ospf6_router_lsa
);
978 total_lsa_length
= lsa_length
;
979 type
= htons(OSPF6_LSTYPE_ROUTER
);
981 /* First check Aggregated LSA formed earlier in Cache */
982 lsa
= ospf6_lsdb_lookup(type
, htonl(0), adv_router
,
983 area
->temp_router_lsa_lsdb
);
987 inet_ntop(AF_INET
, &adv_router
, ifbuf
, sizeof(ifbuf
));
989 /* Determine total LSA length from all link state ids */
990 end
= ospf6_lsdb_head(lsdb
, 2, type
, adv_router
, &rtr_lsa
);
993 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
994 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
997 lsa_header
= (struct ospf6_lsa_header
*)rtr_lsa
->header
;
998 total_lsa_length
+= (ntohs(lsa_header
->length
) - lsa_length
);
1000 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1002 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1003 zlog_debug("%s: adv_router %s num_lsa %u to convert.",
1004 __PRETTY_FUNCTION__
, ifbuf
, num_lsa
);
1009 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1010 zlog_debug("%s: adv_router %s not found in LSDB.",
1011 __PRETTY_FUNCTION__
, ifbuf
);
1015 /* Allocate memory for this LSA */
1016 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
));
1022 lsa
->header
= (struct ospf6_lsa_header
*)new_header
;
1024 lsa
->lsdb
= area
->temp_router_lsa_lsdb
;
1026 /* Fill Larger LSA Payload */
1027 end
= ospf6_lsdb_head(lsdb
, 2, type
, adv_router
, &rtr_lsa
);
1030 * We assume at this point in time that rtr_lsa is
1034 if (!OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
1035 /* Append first Link State ID LSA */
1036 lsa_header
= (struct ospf6_lsa_header
*)rtr_lsa
->header
;
1037 memcpy(new_header
, lsa_header
, ntohs(lsa_header
->length
));
1038 /* Assign new lsa length as aggregated length. */
1039 ((struct ospf6_lsa_header
*)new_header
)->length
=
1040 htons(total_lsa_length
);
1041 new_header
+= ntohs(lsa_header
->length
);
1045 /* Print LSA Name */
1046 ospf6_lsa_printbuf(lsa
, lsa
->name
, sizeof(lsa
->name
));
1048 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1050 if (OSPF6_LSA_IS_MAXAGE(rtr_lsa
)) {
1051 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1055 if (IS_OSPF6_DEBUG_SPF(PROCESS
)) {
1056 lsd
= OSPF6_LSA_HEADER_END(rtr_lsa
->header
) + 4;
1057 interface_id
= ROUTER_LSDESC_GET_IFID(lsd
);
1058 inet_ntop(AF_INET
, &interface_id
, ifbuf
, sizeof(ifbuf
));
1060 "%s: Next Router LSA %s to aggreat with len %u interface_id %s",
1061 __PRETTY_FUNCTION__
, rtr_lsa
->name
,
1062 ntohs(lsa_header
->length
), ifbuf
);
1065 /* Append Next Link State ID LSA */
1066 lsa_header
= (struct ospf6_lsa_header
*)rtr_lsa
->header
;
1067 memcpy(new_header
, (OSPF6_LSA_HEADER_END(rtr_lsa
->header
) + 4),
1068 (ntohs(lsa_header
->length
) - lsa_length
));
1069 new_header
+= (ntohs(lsa_header
->length
) - lsa_length
);
1072 rtr_lsa
= ospf6_lsdb_next(end
, rtr_lsa
);
1075 /* Calculate birth of this lsa */
1076 ospf6_lsa_age_set(lsa
);
1078 /* Store Aggregated LSA into area temp lsdb */
1079 ospf6_lsdb_add(lsa
, area
->temp_router_lsa_lsdb
);
1081 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1082 zlog_debug("%s: LSA %s id %u type 0%x len %u num_lsa %u",
1083 __PRETTY_FUNCTION__
, lsa
->name
,
1084 ntohl(lsa
->header
->id
), ntohs(lsa
->header
->type
),
1085 ntohs(lsa
->header
->length
), num_lsa
);
1090 void ospf6_remove_temp_router_lsa(struct ospf6_area
*area
)
1092 struct ospf6_lsa
*lsa
= NULL
;
1094 for (ALL_LSDB(area
->temp_router_lsa_lsdb
, lsa
)) {
1095 if (IS_OSPF6_DEBUG_SPF(PROCESS
))
1097 "%s Remove LSA %s lsa->lock %u lsdb count %u",
1098 __PRETTY_FUNCTION__
, lsa
->name
, lsa
->lock
,
1099 area
->temp_router_lsa_lsdb
->count
);
1100 ospf6_lsdb_remove(lsa
, area
->temp_router_lsa_lsdb
);