1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /* OSPF SPF calculation.
3 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
17 #include "sockunion.h" /* for inet_ntop () */
19 #include "ospfd/ospfd.h"
20 #include "ospfd/ospf_interface.h"
21 #include "ospfd/ospf_ism.h"
22 #include "ospfd/ospf_asbr.h"
23 #include "ospfd/ospf_lsa.h"
24 #include "ospfd/ospf_lsdb.h"
25 #include "ospfd/ospf_neighbor.h"
26 #include "ospfd/ospf_nsm.h"
27 #include "ospfd/ospf_spf.h"
28 #include "ospfd/ospf_route.h"
29 #include "ospfd/ospf_ia.h"
30 #include "ospfd/ospf_ase.h"
31 #include "ospfd/ospf_abr.h"
32 #include "ospfd/ospf_dump.h"
33 #include "ospfd/ospf_sr.h"
34 #include "ospfd/ospf_ti_lfa.h"
35 #include "ospfd/ospf_errors.h"
37 #ifdef SUPPORT_OSPF_API
38 #include "ospfd/ospf_apiserver.h"
41 /* Variables to ensure a SPF scheduled log message is printed only once */
43 static unsigned int spf_reason_flags
= 0;
45 /* dummy vertex to flag "in spftree" */
46 static const struct vertex vertex_in_spftree
= {};
47 #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
48 #define LSA_SPF_NOT_EXPLORED NULL
50 static void ospf_clear_spf_reason_flags(void)
55 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
57 spf_reason_flags
|= 1 << reason
;
60 static void ospf_vertex_free(void *);
63 * Heap related functions, for the managment of the candidates, to
64 * be used with pqueue.
66 static int vertex_cmp(const struct vertex
*v1
, const struct vertex
*v2
)
68 if (v1
->distance
!= v2
->distance
)
69 return v1
->distance
- v2
->distance
;
71 if (v1
->type
!= v2
->type
) {
73 case OSPF_VERTEX_NETWORK
:
75 case OSPF_VERTEX_ROUTER
:
81 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue
, struct vertex
, pqi
, vertex_cmp
);
83 static void lsdb_clean_stat(struct ospf_lsdb
*lsdb
)
85 struct route_table
*table
;
86 struct route_node
*rn
;
90 for (i
= OSPF_MIN_LSA
; i
< OSPF_MAX_LSA
; i
++) {
91 table
= lsdb
->type
[i
].db
;
92 for (rn
= route_top(table
); rn
; rn
= route_next(rn
))
93 if ((lsa
= (rn
->info
)) != NULL
)
94 lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
98 static struct vertex_nexthop
*vertex_nexthop_new(void)
100 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
103 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
105 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
109 * Free the canonical nexthop objects for an area, ie the nexthop objects
110 * attached to the first-hop router vertices, and any intervening network
113 static void ospf_canonical_nexthops_free(struct vertex
*root
)
115 struct listnode
*node
, *nnode
;
116 struct vertex
*child
;
118 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
119 struct listnode
*n2
, *nn2
;
120 struct vertex_parent
*vp
;
123 * router vertices through an attached network each
124 * have a distinct (canonical / not inherited) nexthop
125 * which must be freed.
127 * A network vertex can only have router vertices as its
128 * children, so only one level of recursion is possible.
130 if (child
->type
== OSPF_VERTEX_NETWORK
)
131 ospf_canonical_nexthops_free(child
);
133 /* Free child nexthops pointing back to this root vertex */
134 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
)) {
135 if (vp
->parent
== root
&& vp
->nexthop
) {
136 vertex_nexthop_free(vp
->nexthop
);
138 if (vp
->local_nexthop
) {
139 vertex_nexthop_free(vp
->local_nexthop
);
140 vp
->local_nexthop
= NULL
;
148 * TODO: Parent list should be excised, in favour of maintaining only
149 * vertex_nexthop, with refcounts.
151 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
152 struct vertex_nexthop
*hop
,
153 struct vertex_nexthop
*lhop
)
155 struct vertex_parent
*new;
157 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
160 new->backlink
= backlink
;
162 new->local_nexthop
= lhop
;
167 static void vertex_parent_free(struct vertex_parent
*p
)
169 vertex_nexthop_free(p
->local_nexthop
);
170 vertex_nexthop_free(p
->nexthop
);
171 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
174 int vertex_parent_cmp(void *aa
, void *bb
)
176 struct vertex_parent
*a
= aa
, *b
= bb
;
177 return IPV4_ADDR_CMP(&a
->nexthop
->router
, &b
->nexthop
->router
);
180 static struct vertex
*ospf_vertex_new(struct ospf_area
*area
,
181 struct ospf_lsa
*lsa
)
185 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
188 new->type
= lsa
->data
->type
;
189 new->id
= lsa
->data
->id
;
190 new->lsa
= lsa
->data
;
191 new->children
= list_new();
192 new->parents
= list_new();
193 new->parents
->del
= (void (*)(void *))vertex_parent_free
;
194 new->parents
->cmp
= vertex_parent_cmp
;
199 listnode_add(area
->spf_vertex_list
, new);
201 if (IS_DEBUG_OSPF_EVENT
)
202 zlog_debug("%s: Created %s vertex %pI4", __func__
,
203 new->type
== OSPF_VERTEX_ROUTER
? "Router"
210 static void ospf_vertex_free(void *data
)
212 struct vertex
*v
= data
;
214 if (IS_DEBUG_OSPF_EVENT
)
215 zlog_debug("%s: Free %s vertex %pI4", __func__
,
216 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
220 list_delete(&v
->children
);
223 list_delete(&v
->parents
);
227 XFREE(MTYPE_OSPF_VERTEX
, v
);
230 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
231 int print_parents
, int print_children
)
233 if (!IS_DEBUG_OSPF_EVENT
)
236 zlog_debug("%s %s vertex %pI4 distance %u flags %u", msg
,
237 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
238 &v
->lsa
->id
, v
->distance
, (unsigned int)v
->flags
);
241 struct listnode
*node
;
242 struct vertex_parent
*vp
;
244 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
247 "parent %pI4 backlink %d nexthop %pI4 lsa pos %d",
248 &vp
->parent
->lsa
->id
, vp
->backlink
,
249 &vp
->nexthop
->router
,
250 vp
->nexthop
->lsa_pos
);
255 if (print_children
) {
256 struct listnode
*cnode
;
259 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
260 ospf_vertex_dump(" child:", cv
, 0, 0);
265 /* Add a vertex to the list of children in each of its parents. */
266 static void ospf_vertex_add_parent(struct vertex
*v
)
268 struct vertex_parent
*vp
;
269 struct listnode
*node
;
271 assert(v
&& v
->parents
);
273 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
274 assert(vp
->parent
&& vp
->parent
->children
);
276 /* No need to add two links from the same parent. */
277 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
278 listnode_add(vp
->parent
->children
, v
);
282 /* Find a vertex according to its router id */
283 struct vertex
*ospf_spf_vertex_find(struct in_addr id
, struct list
*vertex_list
)
285 struct listnode
*node
;
286 struct vertex
*found
;
288 for (ALL_LIST_ELEMENTS_RO(vertex_list
, node
, found
)) {
289 if (found
->id
.s_addr
== id
.s_addr
)
296 /* Find a vertex parent according to its router id */
297 struct vertex_parent
*ospf_spf_vertex_parent_find(struct in_addr id
,
298 struct vertex
*vertex
)
300 struct listnode
*node
;
301 struct vertex_parent
*found
;
303 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, found
)) {
304 if (found
->parent
->id
.s_addr
== id
.s_addr
)
311 struct vertex
*ospf_spf_vertex_by_nexthop(struct vertex
*root
,
312 struct in_addr
*nexthop
)
314 struct listnode
*node
;
315 struct vertex
*child
;
316 struct vertex_parent
*vertex_parent
;
318 for (ALL_LIST_ELEMENTS_RO(root
->children
, node
, child
)) {
319 vertex_parent
= ospf_spf_vertex_parent_find(root
->id
, child
);
320 if (vertex_parent
->nexthop
->router
.s_addr
== nexthop
->s_addr
)
327 /* Create a deep copy of a SPF vertex without children and parents */
328 static struct vertex
*ospf_spf_vertex_copy(struct vertex
*vertex
)
332 copy
= XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
334 memcpy(copy
, vertex
, sizeof(struct vertex
));
335 copy
->parents
= list_new();
336 copy
->parents
->del
= (void (*)(void *))vertex_parent_free
;
337 copy
->parents
->cmp
= vertex_parent_cmp
;
338 copy
->children
= list_new();
343 /* Create a deep copy of a SPF vertex_parent */
344 static struct vertex_parent
*
345 ospf_spf_vertex_parent_copy(struct vertex_parent
*vertex_parent
)
347 struct vertex_parent
*vertex_parent_copy
;
348 struct vertex_nexthop
*nexthop_copy
, *local_nexthop_copy
;
351 XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex_parent
));
353 nexthop_copy
= vertex_nexthop_new();
354 local_nexthop_copy
= vertex_nexthop_new();
356 memcpy(vertex_parent_copy
, vertex_parent
, sizeof(struct vertex_parent
));
357 memcpy(nexthop_copy
, vertex_parent
->nexthop
,
358 sizeof(struct vertex_nexthop
));
359 memcpy(local_nexthop_copy
, vertex_parent
->local_nexthop
,
360 sizeof(struct vertex_nexthop
));
362 vertex_parent_copy
->nexthop
= nexthop_copy
;
363 vertex_parent_copy
->local_nexthop
= local_nexthop_copy
;
365 return vertex_parent_copy
;
368 /* Create a deep copy of a SPF tree */
369 void ospf_spf_copy(struct vertex
*vertex
, struct list
*vertex_list
)
371 struct listnode
*node
;
372 struct vertex
*vertex_copy
, *child
, *child_copy
, *parent_copy
;
373 struct vertex_parent
*vertex_parent
, *vertex_parent_copy
;
375 /* First check if the node is already in the vertex list */
376 vertex_copy
= ospf_spf_vertex_find(vertex
->id
, vertex_list
);
378 vertex_copy
= ospf_spf_vertex_copy(vertex
);
379 listnode_add(vertex_list
, vertex_copy
);
382 /* Copy all parents, create parent nodes if necessary */
383 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, vertex_parent
)) {
384 parent_copy
= ospf_spf_vertex_find(vertex_parent
->parent
->id
,
388 ospf_spf_vertex_copy(vertex_parent
->parent
);
389 listnode_add(vertex_list
, parent_copy
);
391 vertex_parent_copy
= ospf_spf_vertex_parent_copy(vertex_parent
);
392 vertex_parent_copy
->parent
= parent_copy
;
393 listnode_add(vertex_copy
->parents
, vertex_parent_copy
);
396 /* Copy all children, create child nodes if necessary */
397 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
398 child_copy
= ospf_spf_vertex_find(child
->id
, vertex_list
);
400 child_copy
= ospf_spf_vertex_copy(child
);
401 listnode_add(vertex_list
, child_copy
);
403 listnode_add(vertex_copy
->children
, child_copy
);
406 /* Finally continue copying with child nodes */
407 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
))
408 ospf_spf_copy(child
, vertex_list
);
411 static void ospf_spf_remove_branch(struct vertex_parent
*vertex_parent
,
412 struct vertex
*child
,
413 struct list
*vertex_list
)
415 struct listnode
*node
, *nnode
, *inner_node
, *inner_nnode
;
416 struct vertex
*grandchild
;
417 struct vertex_parent
*vertex_parent_found
;
418 bool has_more_links
= false;
421 * First check if there are more nexthops for that parent to that child
423 for (ALL_LIST_ELEMENTS_RO(child
->parents
, node
, vertex_parent_found
)) {
424 if (vertex_parent_found
->parent
->id
.s_addr
425 == vertex_parent
->parent
->id
.s_addr
426 && vertex_parent_found
->nexthop
->router
.s_addr
427 != vertex_parent
->nexthop
->router
.s_addr
)
428 has_more_links
= true;
432 * No more links from that parent? Then delete the child from its
436 listnode_delete(vertex_parent
->parent
->children
, child
);
439 * Delete the vertex_parent from the child parents list, this needs to
442 listnode_delete(child
->parents
, vertex_parent
);
445 * Are there actually more parents left? If not, then delete the child!
446 * This is done by recursively removing the links to the grandchildren,
447 * such that finally the child can be removed without leaving unused
450 if (child
->parents
->count
== 0) {
451 for (ALL_LIST_ELEMENTS(child
->children
, node
, nnode
,
453 for (ALL_LIST_ELEMENTS(grandchild
->parents
, inner_node
,
455 vertex_parent_found
)) {
456 ospf_spf_remove_branch(vertex_parent_found
,
457 grandchild
, vertex_list
);
460 listnode_delete(vertex_list
, child
);
461 ospf_vertex_free(child
);
465 static int ospf_spf_remove_link(struct vertex
*vertex
, struct list
*vertex_list
,
466 struct router_lsa_link
*link
)
468 struct listnode
*node
, *inner_node
;
469 struct vertex
*child
;
470 struct vertex_parent
*vertex_parent
;
473 * Identify the node who shares a subnet (given by the link) with a
474 * child and remove the branch of this particular child.
476 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
477 for (ALL_LIST_ELEMENTS_RO(child
->parents
, inner_node
,
479 if ((vertex_parent
->local_nexthop
->router
.s_addr
480 & link
->link_data
.s_addr
)
481 == (link
->link_id
.s_addr
482 & link
->link_data
.s_addr
)) {
483 ospf_spf_remove_branch(vertex_parent
, child
,
490 /* No link found yet, move on recursively */
491 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
492 if (ospf_spf_remove_link(child
, vertex_list
, link
) == 0)
496 /* link was not removed yet */
500 void ospf_spf_remove_resource(struct vertex
*vertex
, struct list
*vertex_list
,
501 struct protected_resource
*resource
)
503 struct listnode
*node
, *nnode
;
504 struct vertex
*found
;
505 struct vertex_parent
*vertex_parent
;
507 switch (resource
->type
) {
508 case OSPF_TI_LFA_LINK_PROTECTION
:
509 ospf_spf_remove_link(vertex
, vertex_list
, resource
->link
);
511 case OSPF_TI_LFA_NODE_PROTECTION
:
512 found
= ospf_spf_vertex_find(resource
->router_id
, vertex_list
);
517 * Remove the node by removing all links from its parents. Note
518 * that the child is automatically removed here with the last
519 * link from a parent, hence no explicit removal of the node.
521 for (ALL_LIST_ELEMENTS(found
->parents
, node
, nnode
,
523 ospf_spf_remove_branch(vertex_parent
, found
,
527 case OSPF_TI_LFA_UNDEFINED_PROTECTION
:
533 static void ospf_spf_init(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
534 bool is_dry_run
, bool is_root_node
)
536 struct list
*vertex_list
;
539 /* Create vertex list */
540 vertex_list
= list_new();
541 vertex_list
->del
= ospf_vertex_free
;
542 area
->spf_vertex_list
= vertex_list
;
544 /* Create root node. */
545 v
= ospf_vertex_new(area
, root_lsa
);
548 area
->spf_dry_run
= is_dry_run
;
549 area
->spf_root_node
= is_root_node
;
551 /* Reset ABR and ASBR router counts. */
553 area
->asbr_count
= 0;
556 /* return index of link back to V from W, or -1 if no link found */
557 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
559 unsigned int i
, length
;
560 struct router_lsa
*rl
;
561 struct network_lsa
*nl
;
563 /* In case of W is Network LSA. */
564 if (w
->type
== OSPF_NETWORK_LSA
) {
565 if (v
->type
== OSPF_NETWORK_LSA
)
568 nl
= (struct network_lsa
*)w
;
569 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
571 for (i
= 0; i
< length
; i
++)
572 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
577 /* In case of W is Router LSA. */
578 if (w
->type
== OSPF_ROUTER_LSA
) {
579 rl
= (struct router_lsa
*)w
;
581 length
= ntohs(w
->length
);
583 for (i
= 0; i
< ntohs(rl
->links
)
584 && length
>= sizeof(struct router_lsa
);
586 switch (rl
->link
[i
].type
) {
587 case LSA_LINK_TYPE_POINTOPOINT
:
588 case LSA_LINK_TYPE_VIRTUALLINK
:
590 if (v
->type
== OSPF_ROUTER_LSA
591 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
596 case LSA_LINK_TYPE_TRANSIT
:
597 /* Network LSA ID. */
598 if (v
->type
== OSPF_NETWORK_LSA
599 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
604 case LSA_LINK_TYPE_STUB
:
605 /* Stub can't lead anywhere, carry on */
616 * Find the next link after prev_link from v to w. If prev_link is
617 * NULL, return the first link from v to w. Ignore stub and virtual links;
618 * these link types will never be returned.
620 static struct router_lsa_link
*
621 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
622 struct router_lsa_link
*prev_link
)
626 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
627 struct router_lsa_link
*l
;
629 if (w
->type
== OSPF_VERTEX_ROUTER
)
630 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
632 if (prev_link
== NULL
)
633 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
635 p
= (uint8_t *)prev_link
;
636 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
637 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
640 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
643 l
= (struct router_lsa_link
*)p
;
645 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
646 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
648 if (l
->m
[0].type
!= lsa_type
)
651 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
658 static void ospf_spf_flush_parents(struct vertex
*w
)
660 struct vertex_parent
*vp
;
661 struct listnode
*ln
, *nn
;
663 /* delete the existing nexthops */
664 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
665 list_delete_node(w
->parents
, ln
);
666 vertex_parent_free(vp
);
671 * Consider supplied next-hop for inclusion to the supplied list of
672 * equal-cost next-hops, adjust list as necessary.
674 * Returns vertex parent pointer if created otherwise `NULL` if it already
677 static struct vertex_parent
*ospf_spf_add_parent(struct vertex
*v
,
679 struct vertex_nexthop
*newhop
,
680 struct vertex_nexthop
*newlhop
,
681 unsigned int distance
)
683 struct vertex_parent
*vp
, *wp
;
684 struct listnode
*node
;
686 /* we must have a newhop, and a distance */
687 assert(v
&& w
&& newhop
);
691 * IFF w has already been assigned a distance, then we shouldn't get
692 * here unless callers have determined V(l)->W is shortest /
693 * equal-shortest path (0 is a special case distance (no distance yet
697 assert(distance
<= w
->distance
);
699 w
->distance
= distance
;
701 if (IS_DEBUG_OSPF_EVENT
)
702 zlog_debug("%s: Adding %pI4 as parent of %pI4", __func__
,
703 &v
->lsa
->id
, &w
->lsa
->id
);
706 * Adding parent for a new, better path: flush existing parents from W.
708 if (distance
< w
->distance
) {
709 if (IS_DEBUG_OSPF_EVENT
)
711 "%s: distance %d better than %d, flushing existing parents",
712 __func__
, distance
, w
->distance
);
713 ospf_spf_flush_parents(w
);
714 w
->distance
= distance
;
718 * new parent is <= existing parents, add it to parent list (if nexthop
719 * not on parent list)
721 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
722 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
723 if (IS_DEBUG_OSPF_EVENT
)
725 "%s: ... nexthop already on parent list, skipping add",
732 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
,
734 listnode_add_sort(w
->parents
, vp
);
739 static int match_stub_prefix(struct lsa_header
*lsa
, struct in_addr v_link_addr
,
740 struct in_addr w_link_addr
)
743 struct router_lsa_link
*l
= NULL
;
744 struct in_addr masked_lsa_addr
;
746 if (lsa
->type
!= OSPF_ROUTER_LSA
)
749 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
750 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
753 l
= (struct router_lsa_link
*)p
;
754 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
755 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
757 if (l
->m
[0].type
!= LSA_LINK_TYPE_STUB
)
760 masked_lsa_addr
.s_addr
=
761 (l
->link_id
.s_addr
& l
->link_data
.s_addr
);
763 /* check that both links belong to the same stub subnet */
764 if ((masked_lsa_addr
.s_addr
765 == (v_link_addr
.s_addr
& l
->link_data
.s_addr
))
766 && (masked_lsa_addr
.s_addr
767 == (w_link_addr
.s_addr
& l
->link_data
.s_addr
)))
775 * 16.1.1. Calculate nexthop from root through V (parent) to
776 * vertex W (destination), with given distance from root->W.
778 * The link must be supplied if V is the root vertex. In all other cases
781 * Note that this function may fail, hence the state of the destination
782 * vertex, W, should /not/ be modified in a dependent manner until
783 * this function returns. This function will update the W vertex with the
784 * provided distance as appropriate.
786 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
787 struct vertex
*v
, struct vertex
*w
,
788 struct router_lsa_link
*l
,
789 unsigned int distance
, int lsa_pos
)
791 struct listnode
*node
, *nnode
;
792 struct vertex_nexthop
*nh
, *lnh
;
793 struct vertex_parent
*vp
;
794 unsigned int added
= 0;
796 if (IS_DEBUG_OSPF_EVENT
) {
797 zlog_debug("%s: Start", __func__
);
798 ospf_vertex_dump("V (parent):", v
, 1, 1);
799 ospf_vertex_dump("W (dest) :", w
, 1, 1);
800 zlog_debug("V->W distance: %d", distance
);
803 if (v
== area
->spf
) {
805 * 16.1.1 para 4. In the first case, the parent vertex (V) is
806 * the root (the calculating router itself). This means that
807 * the destination is either a directly connected network or
808 * directly connected router. The outgoing interface in this
809 * case is simply the OSPF interface connecting to the
810 * destination network/router.
813 /* we *must* be supplied with the link data */
816 if (IS_DEBUG_OSPF_EVENT
)
818 "%s: considering link type:%d link_id:%pI4 link_data:%pI4",
819 __func__
, l
->m
[0].type
, &l
->link_id
,
822 if (w
->type
== OSPF_VERTEX_ROUTER
) {
824 * l is a link from v to w l2 will be link from w to v
826 struct router_lsa_link
*l2
= NULL
;
828 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
829 struct ospf_interface
*oi
= NULL
;
830 struct in_addr nexthop
= {.s_addr
= 0};
832 if (area
->spf_root_node
) {
833 oi
= ospf_if_lookup_by_lsa_pos(area
,
837 "%s: OI not found in LSA: lsa_pos: %d link_id:%pI4 link_data:%pI4",
846 * If the destination is a router which connects
847 * to the calculating router via a
848 * Point-to-MultiPoint network, the
849 * destination's next hop IP address(es) can be
850 * determined by examining the destination's
851 * router-LSA: each link pointing back to the
852 * calculating router and having a Link Data
853 * field belonging to the Point-to-MultiPoint
854 * network provides an IP address of the next
857 * At this point l is a link from V to W, and V
858 * is the root ("us"). If it is a point-to-
859 * multipoint interface, then look through the
860 * links in the opposite direction (W to V).
861 * If any of them have an address that lands
862 * within the subnet declared by the PtMP link,
863 * then that link is a constituent of the PtMP
864 * link, and its address is a nexthop address
867 * Note for point-to-point interfaces:
869 * Having nexthop = 0 (as proposed in the RFC)
870 * is tempting, but NOT acceptable. It breaks
871 * AS-External routes with a forwarding address,
872 * since ospf_ase_complete_direct_routes() will
873 * mistakenly assume we've reached the last hop
874 * and should place the forwarding address as
875 * nexthop. Also, users may configure multi-
876 * access links in p2p mode, so we need the IP
877 * to ARP the nexthop.
879 * If the calculating router is the SPF root
880 * node and the link is P2P then access the
881 * interface information directly. This can be
882 * crucial when e.g. IP unnumbered is used
883 * where 'correct' nexthop information are not
884 * available via Router LSAs.
886 * Otherwise handle P2P and P2MP the same way
887 * as described above using a reverse lookup to
888 * figure out the nexthop.
892 * HACK: we don't know (yet) how to distinguish
893 * between P2P and P2MP interfaces by just
894 * looking at LSAs, which is important for
895 * TI-LFA since you want to do SPF calculations
896 * from the perspective of other nodes. Since
897 * TI-LFA is currently not implemented for P2MP
898 * we just check here if it is enabled and then
899 * blindly assume that P2P is used. Ultimately
900 * the interface code needs to be removed
903 if (area
->ospf
->ti_lfa_enabled
904 || (oi
&& oi
->type
== OSPF_IFTYPE_POINTOPOINT
)
905 || (oi
&& oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
906 && oi
->address
->prefixlen
== IPV4_MAX_BITLEN
)) {
907 struct ospf_neighbor
*nbr_w
= NULL
;
909 /* Calculating node is root node, link
911 if (area
->spf_root_node
) {
912 nbr_w
= ospf_nbr_lookup_by_routerid(
913 oi
->nbrs
, &l
->link_id
);
916 nexthop
= nbr_w
->src
;
922 while ((l2
= ospf_get_next_link(
924 if (match_stub_prefix(
935 } else if (oi
&& oi
->type
936 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
937 struct prefix_ipv4 la
;
940 la
.prefixlen
= oi
->address
->prefixlen
;
943 * V links to W on PtMP interface;
944 * find the interface address on W
946 while ((l2
= ospf_get_next_link(w
, v
,
948 la
.prefix
= l2
->link_data
;
950 if (prefix_cmp((struct prefix
956 nexthop
= l2
->link_data
;
962 nh
= vertex_nexthop_new();
963 nh
->router
= nexthop
;
964 nh
->lsa_pos
= lsa_pos
;
967 * Since v is the root the nexthop and
968 * local nexthop are the same.
970 lnh
= vertex_nexthop_new();
972 sizeof(struct vertex_nexthop
));
974 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
977 vertex_nexthop_free(nh
);
978 vertex_nexthop_free(lnh
);
983 "%s: could not determine nexthop for link %s",
984 __func__
, oi
? oi
->ifp
->name
: "");
985 } /* end point-to-point link from V to W */
986 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
988 * VLink implementation limitations:
989 * a) vl_data can only reference one nexthop,
990 * so no ECMP to backbone through VLinks.
991 * Though transit-area summaries may be
992 * considered, and those can be ECMP.
993 * b) We can only use /one/ VLink, even if
994 * multiple ones exist this router through
995 * multiple transit-areas.
998 struct ospf_vl_data
*vl_data
;
1000 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
1004 && CHECK_FLAG(vl_data
->flags
,
1005 OSPF_VL_FLAG_APPROVED
)) {
1006 nh
= vertex_nexthop_new();
1007 nh
->router
= vl_data
->nexthop
.router
;
1008 nh
->lsa_pos
= vl_data
->nexthop
.lsa_pos
;
1011 * Since v is the root the nexthop and
1012 * local nexthop are the same.
1014 lnh
= vertex_nexthop_new();
1016 sizeof(struct vertex_nexthop
));
1018 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
1021 vertex_nexthop_free(nh
);
1022 vertex_nexthop_free(lnh
);
1028 "%s: vl_data for VL link not found",
1030 } /* end virtual-link from V to W */
1032 } /* end W is a Router vertex */
1034 assert(w
->type
== OSPF_VERTEX_NETWORK
);
1036 nh
= vertex_nexthop_new();
1037 nh
->router
.s_addr
= 0; /* Nexthop not required */
1038 nh
->lsa_pos
= lsa_pos
;
1041 * Since v is the root the nexthop and
1042 * local nexthop are the same.
1044 lnh
= vertex_nexthop_new();
1045 memcpy(lnh
, nh
, sizeof(struct vertex_nexthop
));
1047 if (ospf_spf_add_parent(v
, w
, nh
, lnh
, distance
) ==
1049 vertex_nexthop_free(nh
);
1050 vertex_nexthop_free(lnh
);
1055 } /* end V is the root */
1056 /* Check if W's parent is a network connected to root. */
1057 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
1058 /* See if any of V's parents are the root. */
1059 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1060 if (vp
->parent
== area
->spf
) {
1062 * 16.1.1 para 5. ...the parent vertex is a
1063 * network that directly connects the
1064 * calculating router to the destination
1065 * router. The list of next hops is then
1066 * determined by examining the destination's
1070 assert(w
->type
== OSPF_VERTEX_ROUTER
);
1071 while ((l
= ospf_get_next_link(w
, v
, l
))) {
1073 * ... For each link in the router-LSA
1074 * that points back to the parent
1075 * network, the link's Link Data field
1076 * provides the IP address of a next hop
1077 * router. The outgoing interface to use
1078 * can then be derived from the next
1079 * hop IP address (or it can be
1080 * inherited from the parent network).
1082 nh
= vertex_nexthop_new();
1083 nh
->router
= l
->link_data
;
1084 nh
->lsa_pos
= vp
->nexthop
->lsa_pos
;
1087 * Since v is the root the nexthop and
1088 * local nexthop are the same.
1090 lnh
= vertex_nexthop_new();
1092 sizeof(struct vertex_nexthop
));
1095 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
1098 vertex_nexthop_free(nh
);
1099 vertex_nexthop_free(lnh
);
1103 * Note lack of return is deliberate. See next
1109 * NB: This code is non-trivial.
1111 * E.g. it is not enough to know that V connects to the root. It
1112 * is also important that the while above, looping through all
1113 * links from W->V found at least one link, so that we know
1114 * there is bi-directional connectivity between V and W (which
1115 * need not be the case, e.g. when OSPF has not yet converged
1116 * fully). Otherwise, if we /always/ return here, without having
1117 * checked that root->V->-W actually resulted in a valid nexthop
1118 * being created, then we we will prevent SPF from finding/using
1119 * higher cost paths.
1121 * It is important, if root->V->W has not been added, that we
1122 * continue through to the intervening-router nexthop code
1123 * below. So as to ensure other paths to V may be used. This
1124 * avoids unnecessary blackholes while OSPF is converging.
1126 * I.e. we may have arrived at this function, examining V -> W,
1127 * via workable paths other than root -> V, and it's important
1128 * to avoid getting "confused" by non-working root->V->W path
1129 * - it's important to *not* lose the working non-root paths,
1130 * just because of a non-viable root->V->W.
1137 * 16.1.1 para 4. If there is at least one intervening router in the
1138 * current shortest path between the destination and the root, the
1139 * destination simply inherits the set of next hops from the
1142 if (IS_DEBUG_OSPF_EVENT
)
1143 zlog_debug("%s: Intervening routers, adding parent(s)",
1146 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1150 * The nexthop is inherited, but the local nexthop still needs
1154 lnh
= vertex_nexthop_new();
1155 lnh
->router
= l
->link_data
;
1156 lnh
->lsa_pos
= lsa_pos
;
1161 nh
= vertex_nexthop_new();
1164 if (ospf_spf_add_parent(v
, w
, nh
, lnh
, distance
) == NULL
) {
1165 vertex_nexthop_free(nh
);
1166 vertex_nexthop_free(lnh
);
1173 static int ospf_spf_is_protected_resource(struct ospf_area
*area
,
1174 struct router_lsa_link
*link
,
1175 struct lsa_header
*lsa
)
1178 struct router_lsa_link
*p_link
;
1179 struct router_lsa_link
*l
= NULL
;
1180 struct in_addr router_id
;
1183 if (!area
->spf_protected_resource
)
1186 link_type
= link
->m
[0].type
;
1188 switch (area
->spf_protected_resource
->type
) {
1189 case OSPF_TI_LFA_LINK_PROTECTION
:
1190 p_link
= area
->spf_protected_resource
->link
;
1194 /* For P2P: check if the link belongs to the same subnet */
1195 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1196 && (p_link
->link_id
.s_addr
& p_link
->link_data
.s_addr
)
1197 == (link
->link_data
.s_addr
1198 & p_link
->link_data
.s_addr
))
1201 /* For stub: check if this the same subnet */
1202 if (link_type
== LSA_LINK_TYPE_STUB
1203 && (p_link
->link_id
.s_addr
== link
->link_id
.s_addr
)
1204 && (p_link
->link_data
.s_addr
== link
->link_data
.s_addr
))
1208 case OSPF_TI_LFA_NODE_PROTECTION
:
1209 router_id
= area
->spf_protected_resource
->router_id
;
1210 if (router_id
.s_addr
== INADDR_ANY
)
1213 /* For P2P: check if the link leads to the protected node */
1214 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1215 && link
->link_id
.s_addr
== router_id
.s_addr
)
1218 /* The rest is about stub links! */
1219 if (link_type
!= LSA_LINK_TYPE_STUB
)
1223 * Check if there's a P2P link in the router LSA with the
1224 * corresponding link data in the same subnet.
1227 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1228 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
1231 l
= (struct router_lsa_link
*)p
;
1232 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1233 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1235 /* We only care about P2P with the proper link id */
1236 if ((l
->m
[0].type
!= LSA_LINK_TYPE_POINTOPOINT
)
1237 || (l
->link_id
.s_addr
!= router_id
.s_addr
))
1240 /* Link data in the subnet given by the link? */
1241 if ((link
->link_id
.s_addr
& link
->link_data
.s_addr
)
1242 == (l
->link_data
.s_addr
& link
->link_data
.s_addr
))
1247 case OSPF_TI_LFA_UNDEFINED_PROTECTION
:
1255 * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
1256 * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
1257 * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
1258 * corresponding link in the LSA of W and extract the particular weight.
1260 * TODO: Only P2P supported by now!
1262 static uint16_t get_reverse_distance(struct vertex
*v
,
1263 struct router_lsa_link
*l
,
1264 struct ospf_lsa
*w_lsa
)
1267 struct router_lsa_link
*w_link
;
1268 uint16_t distance
= 0;
1270 assert(w_lsa
&& w_lsa
->data
);
1272 p
= ((uint8_t *)w_lsa
->data
) + OSPF_LSA_HEADER_SIZE
+ 4;
1273 lim
= ((uint8_t *)w_lsa
->data
) + ntohs(w_lsa
->data
->length
);
1276 w_link
= (struct router_lsa_link
*)p
;
1277 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1278 + (w_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1280 /* Only care about P2P with link ID equal to V's router id */
1281 if (w_link
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
1282 && w_link
->link_id
.s_addr
== v
->id
.s_addr
) {
1283 distance
= ntohs(w_link
->m
[0].metric
);
1289 * This might happen if the LSA for W is not complete yet. In this
1290 * case we take the weight of the 'forward' link from V. When the LSA
1291 * for W is completed the reverse SPF is run again anyway.
1294 distance
= ntohs(l
->m
[0].metric
);
1296 if (IS_DEBUG_OSPF_EVENT
)
1297 zlog_debug("%s: reversed distance is %u", __func__
, distance
);
1304 * v is on the SPF tree. Examine the links in v's LSA. Update the list of
1305 * candidates with any vertices not already on the list. If a lower-cost path
1306 * is found to a vertex already on the candidate list, store the new cost.
1308 static void ospf_spf_next(struct vertex
*v
, struct ospf_area
*area
,
1309 struct vertex_pqueue_head
*candidate
)
1311 struct ospf_lsa
*w_lsa
= NULL
;
1314 struct router_lsa_link
*l
= NULL
;
1316 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
1317 uint16_t link_distance
;
1320 * If this is a router-LSA, and bit V of the router-LSA (see Section
1321 * A.4.2:RFC2328) is set, set Area A's TransitCapability to true.
1323 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1324 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
1325 area
->transit
= OSPF_TRANSIT_TRUE
;
1328 if (IS_DEBUG_OSPF_EVENT
)
1329 zlog_debug("%s: Next vertex of %s vertex %pI4", __func__
,
1330 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
1333 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1334 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1338 unsigned int distance
;
1340 /* In case of V is Router-LSA. */
1341 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
1342 l
= (struct router_lsa_link
*)p
;
1344 lsa_pos
= lsa_pos_next
; /* LSA link position */
1347 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1348 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1351 * (a) If this is a link to a stub network, examine the
1352 * next link in V's LSA. Links to stub networks will
1353 * be considered in the second stage of the shortest
1356 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
1360 * Don't process TI-LFA protected resources.
1362 * TODO: Replace this by a proper solution, e.g. remove
1363 * corresponding links from the LSDB and run the SPF
1364 * algo with the stripped-down LSDB.
1366 if (ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1370 * (b) Otherwise, W is a transit vertex (router or
1371 * transit network). Look up the vertex W's LSA
1372 * (router-LSA or network-LSA) in Area A's link state
1376 case LSA_LINK_TYPE_POINTOPOINT
:
1377 case LSA_LINK_TYPE_VIRTUALLINK
:
1378 if (type
== LSA_LINK_TYPE_VIRTUALLINK
1379 && IS_DEBUG_OSPF_EVENT
)
1381 "looking up LSA through VL: %pI4",
1383 w_lsa
= ospf_lsa_lookup(area
->ospf
, area
,
1385 l
->link_id
, l
->link_id
);
1386 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1387 zlog_debug("found Router LSA %pI4",
1390 case LSA_LINK_TYPE_TRANSIT
:
1391 if (IS_DEBUG_OSPF_EVENT
)
1393 "Looking up Network LSA, ID: %pI4",
1395 w_lsa
= ospf_lsa_lookup_by_id(
1396 area
, OSPF_NETWORK_LSA
, l
->link_id
);
1397 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1398 zlog_debug("found the LSA");
1401 flog_warn(EC_OSPF_LSA
,
1402 "Invalid LSA link type %d", type
);
1407 * For TI-LFA we might need the reverse SPF.
1408 * Currently only works with P2P!
1410 if (type
== LSA_LINK_TYPE_POINTOPOINT
1411 && area
->spf_reversed
)
1413 get_reverse_distance(v
, l
, w_lsa
);
1415 link_distance
= ntohs(l
->m
[0].metric
);
1417 /* step (d) below */
1418 distance
= v
->distance
+ link_distance
;
1420 /* In case of V is Network-LSA. */
1421 r
= (struct in_addr
*)p
;
1422 p
+= sizeof(struct in_addr
);
1424 /* Lookup the vertex W's LSA. */
1425 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
1427 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1428 zlog_debug("found Router LSA %pI4",
1431 /* step (d) below */
1432 distance
= v
->distance
;
1436 * (b cont.) If the LSA does not exist, or its LS age is equal
1437 * to MaxAge, or it does not have a link back to vertex V,
1438 * examine the next link in V's LSA.[23]
1440 if (w_lsa
== NULL
) {
1441 if (IS_DEBUG_OSPF_EVENT
)
1442 zlog_debug("No LSA found");
1446 if (IS_LSA_MAXAGE(w_lsa
)) {
1447 if (IS_DEBUG_OSPF_EVENT
)
1448 zlog_debug("LSA is MaxAge");
1452 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
1453 if (IS_DEBUG_OSPF_EVENT
)
1454 zlog_debug("The LSA doesn't have a link back");
1459 * (c) If vertex W is already on the shortest-path tree, examine
1460 * the next link in the LSA.
1462 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
1463 if (IS_DEBUG_OSPF_EVENT
)
1464 zlog_debug("The LSA is already in SPF");
1469 * (d) Calculate the link state cost D of the resulting path
1470 * from the root to vertex W. D is equal to the sum of the link
1471 * state cost of the (already calculated) shortest path to
1472 * vertex V and the advertised cost of the link between vertices
1476 /* calculate link cost D -- moved above */
1478 /* Is there already vertex W in candidate list? */
1479 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
1480 /* prepare vertex W. */
1481 w
= ospf_vertex_new(area
, w_lsa
);
1483 /* Calculate nexthop to W. */
1484 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
1486 vertex_pqueue_add(candidate
, w
);
1488 listnode_delete(area
->spf_vertex_list
, w
);
1489 ospf_vertex_free(w
);
1490 w_lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
1491 if (IS_DEBUG_OSPF_EVENT
)
1492 zlog_debug("Nexthop Calc failed");
1494 } else if (w_lsa
->stat
!= LSA_SPF_IN_SPFTREE
) {
1496 if (w
->distance
< distance
) {
1499 else if (w
->distance
== distance
) {
1501 * Found an equal-cost path to W.
1502 * Calculate nexthop of to W from V.
1504 ospf_nexthop_calculation(area
, v
, w
, l
,
1509 * Found a lower-cost path to W.
1510 * nexthop_calculation is conditional, if it
1511 * finds valid nexthop it will call
1512 * spf_add_parents, which will flush the old
1515 vertex_pqueue_del(candidate
, w
);
1516 ospf_nexthop_calculation(area
, v
, w
, l
,
1518 vertex_pqueue_add(candidate
, w
);
1520 } /* end W is already on the candidate list */
1521 } /* end loop over the links in V's LSA */
1524 static void ospf_spf_dump(struct vertex
*v
, int i
)
1526 struct listnode
*cnode
;
1527 struct listnode
*nnode
;
1528 struct vertex_parent
*parent
;
1530 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1531 if (IS_DEBUG_OSPF_EVENT
)
1532 zlog_debug("SPF Result: %d [R] %pI4", i
,
1535 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1536 if (IS_DEBUG_OSPF_EVENT
)
1537 zlog_debug("SPF Result: %d [N] %pI4/%d", i
,
1539 ip_masklen(lsa
->mask
));
1542 if (IS_DEBUG_OSPF_EVENT
)
1543 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1544 zlog_debug(" nexthop %p %pI4 %d",
1545 (void *)parent
->nexthop
,
1546 &parent
->nexthop
->router
,
1547 parent
->nexthop
->lsa_pos
);
1552 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1553 ospf_spf_dump(v
, i
);
1556 void ospf_spf_print(struct vty
*vty
, struct vertex
*v
, int i
)
1558 struct listnode
*cnode
;
1559 struct listnode
*nnode
;
1560 struct vertex_parent
*parent
;
1562 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1563 vty_out(vty
, "SPF Result: depth %d [R] %pI4\n", i
, &v
->lsa
->id
);
1565 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1566 vty_out(vty
, "SPF Result: depth %d [N] %pI4/%d\n", i
,
1567 &v
->lsa
->id
, ip_masklen(lsa
->mask
));
1570 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1572 " nexthop %pI4 lsa pos %d -- local nexthop %pI4 lsa pos %d\n",
1573 &parent
->nexthop
->router
, parent
->nexthop
->lsa_pos
,
1574 &parent
->local_nexthop
->router
,
1575 parent
->local_nexthop
->lsa_pos
);
1580 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1581 ospf_spf_print(vty
, v
, i
);
1584 /* Second stage of SPF calculation. */
1585 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1586 struct route_table
*rt
, int parent_is_root
)
1588 struct listnode
*cnode
, *cnnode
;
1589 struct vertex
*child
;
1591 if (IS_DEBUG_OSPF_EVENT
)
1592 zlog_debug("%s: processing stubs for area %pI4", __func__
,
1595 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1598 struct router_lsa_link
*l
;
1599 struct router_lsa
*router_lsa
;
1602 if (IS_DEBUG_OSPF_EVENT
)
1603 zlog_debug("%s: processing router LSA, id: %pI4",
1604 __func__
, &v
->lsa
->id
);
1606 router_lsa
= (struct router_lsa
*)v
->lsa
;
1608 if (IS_DEBUG_OSPF_EVENT
)
1609 zlog_debug("%s: we have %d links to process", __func__
,
1610 ntohs(router_lsa
->links
));
1612 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1613 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1616 l
= (struct router_lsa_link
*)p
;
1618 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1619 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1621 /* Don't process TI-LFA protected resources */
1622 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
1623 && !ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1624 ospf_intra_add_stub(rt
, l
, v
, area
,
1625 parent_is_root
, lsa_pos
);
1630 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1633 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1634 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1638 * The first level of routers connected to the root
1639 * should have 'parent_is_root' set, including those
1640 * connected via a network vertex.
1644 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1647 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1649 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1653 void ospf_rtrs_free(struct route_table
*rtrs
)
1655 struct route_node
*rn
;
1656 struct list
*or_list
;
1657 struct ospf_route
* or ;
1658 struct listnode
*node
, *nnode
;
1660 if (IS_DEBUG_OSPF_EVENT
)
1661 zlog_debug("Route: Router Routing Table free");
1663 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1664 if ((or_list
= rn
->info
) != NULL
) {
1665 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1666 ospf_route_free(or);
1668 list_delete(&or_list
);
1670 /* Unlock the node. */
1672 route_unlock_node(rn
);
1675 route_table_finish(rtrs
);
1678 void ospf_spf_cleanup(struct vertex
*spf
, struct list
*vertex_list
)
1681 * Free nexthop information, canonical versions of which are
1682 * attached the first level of router vertices attached to the
1683 * root vertex, see ospf_nexthop_calculation.
1686 ospf_canonical_nexthops_free(spf
);
1688 /* Free SPF vertices list with deconstructor ospf_vertex_free. */
1690 list_delete(&vertex_list
);
1693 /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */
1694 void ospf_spf_calculate(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
1695 struct route_table
*new_table
,
1696 struct route_table
*all_rtrs
,
1697 struct route_table
*new_rtrs
, bool is_dry_run
,
1700 struct vertex_pqueue_head candidate
;
1703 if (IS_DEBUG_OSPF_EVENT
) {
1704 zlog_debug("%s: Start: running Dijkstra for area %pI4",
1705 __func__
, &area
->area_id
);
1709 * If the router LSA of the root is not yet allocated, return this
1710 * area's calculation. In the 'usual' case the root_lsa is the
1711 * self-originated router LSA of the node itself.
1714 if (IS_DEBUG_OSPF_EVENT
)
1716 "%s: Skip area %pI4's calculation due to empty root LSA",
1717 __func__
, &area
->area_id
);
1721 /* Initialize the algorithm's data structures, see RFC2328 16.1. (1). */
1724 * This function scans all the LSA database and set the stat field to
1725 * LSA_SPF_NOT_EXPLORED.
1727 lsdb_clean_stat(area
->lsdb
);
1729 /* Create a new heap for the candidates. */
1730 vertex_pqueue_init(&candidate
);
1733 * Initialize the shortest-path tree to only the root (which is usually
1734 * the router doing the calculation).
1736 ospf_spf_init(area
, root_lsa
, is_dry_run
, is_root_node
);
1738 /* Set Area A's TransitCapability to false. */
1739 area
->transit
= OSPF_TRANSIT_FALSE
;
1740 area
->shortcut_capability
= 1;
1743 * Use the root vertex for the start of the SPF algorithm and make it
1747 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1750 /* RFC2328 16.1. (2). */
1751 ospf_spf_next(v
, area
, &candidate
);
1753 /* RFC2328 16.1. (3). */
1754 v
= vertex_pqueue_pop(&candidate
);
1756 /* No more vertices left. */
1759 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1761 ospf_vertex_add_parent(v
);
1763 /* RFC2328 16.1. (4). */
1764 if (v
->type
!= OSPF_VERTEX_ROUTER
)
1765 ospf_intra_add_transit(new_table
, v
, area
);
1768 ospf_intra_add_router(new_rtrs
, v
, area
, false);
1770 ospf_intra_add_router(all_rtrs
, v
, area
, true);
1773 /* Iterate back to (2), see RFC2328 16.1. (5). */
1776 if (IS_DEBUG_OSPF_EVENT
) {
1777 ospf_spf_dump(area
->spf
, 0);
1778 ospf_route_table_dump(new_table
);
1780 ospf_router_route_table_dump(all_rtrs
);
1784 * Second stage of SPF calculation procedure's, add leaves to the tree
1785 * for stub networks.
1787 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1789 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1791 /* Increment SPF Calculation Counter. */
1792 area
->spf_calculation
++;
1794 monotime(&area
->ospf
->ts_spf
);
1795 area
->ts_spf
= area
->ospf
->ts_spf
;
1797 if (IS_DEBUG_OSPF_EVENT
)
1798 zlog_debug("%s: Stop. %zd vertices", __func__
,
1799 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1802 void ospf_spf_calculate_area(struct ospf
*ospf
, struct ospf_area
*area
,
1803 struct route_table
*new_table
,
1804 struct route_table
*all_rtrs
,
1805 struct route_table
*new_rtrs
)
1807 ospf_spf_calculate(area
, area
->router_lsa_self
, new_table
, all_rtrs
,
1808 new_rtrs
, false, true);
1810 if (ospf
->ti_lfa_enabled
)
1811 ospf_ti_lfa_compute(area
, new_table
,
1812 ospf
->ti_lfa_protection_type
);
1814 ospf_spf_cleanup(area
->spf
, area
->spf_vertex_list
);
1817 area
->spf_vertex_list
= NULL
;
1820 void ospf_spf_calculate_areas(struct ospf
*ospf
, struct route_table
*new_table
,
1821 struct route_table
*all_rtrs
,
1822 struct route_table
*new_rtrs
)
1824 struct ospf_area
*area
;
1825 struct listnode
*node
, *nnode
;
1827 /* Calculate SPF for each area. */
1828 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1829 /* Do backbone last, so as to first discover intra-area paths
1830 * for any back-bone virtual-links */
1831 if (ospf
->backbone
&& ospf
->backbone
== area
)
1834 ospf_spf_calculate_area(ospf
, area
, new_table
, all_rtrs
,
1838 /* SPF for backbone, if required */
1840 ospf_spf_calculate_area(ospf
, ospf
->backbone
, new_table
,
1841 all_rtrs
, new_rtrs
);
1844 /* Worker for SPF calculation scheduler. */
1845 static void ospf_spf_calculate_schedule_worker(struct event
*thread
)
1847 struct ospf
*ospf
= EVENT_ARG(thread
);
1848 struct route_table
*new_table
, *new_rtrs
;
1849 struct route_table
*all_rtrs
= NULL
;
1850 struct timeval start_time
, spf_start_time
;
1851 unsigned long ia_time
, prune_time
, rt_time
;
1852 unsigned long abr_time
, total_spf_time
, spf_time
;
1853 char rbuf
[32]; /* reason_buf */
1855 if (IS_DEBUG_OSPF_EVENT
)
1856 zlog_debug("SPF: Timer (SPF calculation expire)");
1858 ospf
->t_spf_calc
= NULL
;
1860 ospf_vl_unapprove(ospf
);
1862 /* Execute SPF for each area including backbone, see RFC 2328 16.1. */
1863 monotime(&spf_start_time
);
1864 new_table
= route_table_init(); /* routing table */
1865 new_rtrs
= route_table_init(); /* ABR/ASBR routing table */
1867 /* If we have opaque enabled then track all router reachability */
1868 if (CHECK_FLAG(ospf
->opaque
, OPAQUE_OPERATION_READY_BIT
))
1869 all_rtrs
= route_table_init();
1871 ospf_spf_calculate_areas(ospf
, new_table
, all_rtrs
, new_rtrs
);
1872 spf_time
= monotime_since(&spf_start_time
, NULL
);
1874 ospf_vl_shut_unapproved(ospf
);
1876 /* Calculate inter-area routes, see RFC 2328 16.2. */
1877 monotime(&start_time
);
1878 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1879 ia_time
= monotime_since(&start_time
, NULL
);
1881 /* Get rid of transit networks and routers we cannot reach anyway. */
1882 monotime(&start_time
);
1883 ospf_prune_unreachable_networks(new_table
);
1885 ospf_prune_unreachable_routers(all_rtrs
);
1886 ospf_prune_unreachable_routers(new_rtrs
);
1887 prune_time
= monotime_since(&start_time
, NULL
);
1889 /* Note: RFC 2328 16.3. is apparently missing. */
1892 * Calculate AS external routes, see RFC 2328 16.4.
1893 * There is a dedicated routing table for external routes which is not
1894 * handled here directly
1896 ospf_ase_calculate_schedule(ospf
);
1897 ospf_ase_calculate_timer_add(ospf
);
1899 if (IS_DEBUG_OSPF_EVENT
)
1901 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1902 __func__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1903 ospf
->vrf_id
, new_table
->count
);
1905 /* Update routing table. */
1906 monotime(&start_time
);
1907 ospf_route_install(ospf
, new_table
);
1908 rt_time
= monotime_since(&start_time
, NULL
);
1910 /* Free old all routers routing table */
1911 if (ospf
->oall_rtrs
) {
1912 ospf_rtrs_free(ospf
->oall_rtrs
);
1913 ospf
->oall_rtrs
= NULL
;
1916 /* Update all routers routing table */
1917 ospf
->oall_rtrs
= ospf
->all_rtrs
;
1918 ospf
->all_rtrs
= all_rtrs
;
1919 #ifdef SUPPORT_OSPF_API
1920 ospf_apiserver_notify_reachable(ospf
->oall_rtrs
, ospf
->all_rtrs
);
1923 /* Free old ABR/ASBR routing table */
1924 if (ospf
->old_rtrs
) {
1925 ospf_rtrs_free(ospf
->old_rtrs
);
1926 ospf
->old_rtrs
= NULL
;
1929 /* Update ABR/ASBR routing table */
1930 ospf
->old_rtrs
= ospf
->new_rtrs
;
1931 ospf
->new_rtrs
= new_rtrs
;
1933 /* ABRs may require additional changes, see RFC 2328 16.7. */
1934 monotime(&start_time
);
1935 if (IS_OSPF_ABR(ospf
)) {
1937 ospf_abr_nssa_check_status(ospf
);
1938 ospf_abr_task(ospf
);
1940 abr_time
= monotime_since(&start_time
, NULL
);
1942 /* Schedule Segment Routing update */
1943 ospf_sr_update_task(ospf
);
1946 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1949 if (spf_reason_flags
) {
1950 if (spf_reason_flags
& (1 << SPF_FLAG_ROUTER_LSA_INSTALL
))
1951 strlcat(rbuf
, "R, ", sizeof(rbuf
));
1952 if (spf_reason_flags
& (1 << SPF_FLAG_NETWORK_LSA_INSTALL
))
1953 strlcat(rbuf
, "N, ", sizeof(rbuf
));
1954 if (spf_reason_flags
& (1 << SPF_FLAG_SUMMARY_LSA_INSTALL
))
1955 strlcat(rbuf
, "S, ", sizeof(rbuf
));
1956 if (spf_reason_flags
& (1 << SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
))
1957 strlcat(rbuf
, "AS, ", sizeof(rbuf
));
1958 if (spf_reason_flags
& (1 << SPF_FLAG_ABR_STATUS_CHANGE
))
1959 strlcat(rbuf
, "ABR, ", sizeof(rbuf
));
1960 if (spf_reason_flags
& (1 << SPF_FLAG_ASBR_STATUS_CHANGE
))
1961 strlcat(rbuf
, "ASBR, ", sizeof(rbuf
));
1962 if (spf_reason_flags
& (1 << SPF_FLAG_MAXAGE
))
1963 strlcat(rbuf
, "M, ", sizeof(rbuf
));
1964 if (spf_reason_flags
& (1 << SPF_FLAG_GR_FINISH
))
1965 strlcat(rbuf
, "GR, ", sizeof(rbuf
));
1967 size_t rbuflen
= strlen(rbuf
);
1969 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1974 if (IS_DEBUG_OSPF_EVENT
) {
1975 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1976 zlog_info(" SPF Time: %ld", spf_time
);
1977 zlog_info(" InterArea: %ld", ia_time
);
1978 zlog_info(" Prune: %ld", prune_time
);
1979 zlog_info(" RouteInstall: %ld", rt_time
);
1980 if (IS_OSPF_ABR(ospf
))
1981 zlog_info(" ABR: %ld (%d areas)",
1982 abr_time
, ospf
->areas
->count
);
1983 zlog_info("Reason(s) for SPF: %s", rbuf
);
1986 ospf_clear_spf_reason_flags();
1990 * Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer
1993 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1995 unsigned long delay
, elapsed
, ht
;
1997 if (IS_DEBUG_OSPF_EVENT
)
1998 zlog_debug("SPF: calculation timer scheduled");
2000 /* OSPF instance does not exist. */
2004 ospf_spf_set_reason(reason
);
2006 /* SPF calculation timer is already scheduled. */
2007 if (ospf
->t_spf_calc
) {
2008 if (IS_DEBUG_OSPF_EVENT
)
2010 "SPF: calculation timer is already scheduled: %p",
2011 (void *)ospf
->t_spf_calc
);
2015 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
2017 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
2019 if (ht
> ospf
->spf_max_holdtime
)
2020 ht
= ospf
->spf_max_holdtime
;
2022 /* Get SPF calculation delay time. */
2025 * Got an event within the hold time of last SPF. We need to
2026 * increase the hold_multiplier, if it's not already at/past
2027 * maximum value, and wasn't already increased.
2029 if (ht
< ospf
->spf_max_holdtime
)
2030 ospf
->spf_hold_multiplier
++;
2032 /* always honour the SPF initial delay */
2033 if ((ht
- elapsed
) < ospf
->spf_delay
)
2034 delay
= ospf
->spf_delay
;
2036 delay
= ht
- elapsed
;
2038 /* Event is past required hold-time of last SPF */
2039 delay
= ospf
->spf_delay
;
2040 ospf
->spf_hold_multiplier
= 1;
2043 if (IS_DEBUG_OSPF_EVENT
)
2044 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
2046 ospf
->t_spf_calc
= NULL
;
2047 event_add_timer_msec(master
, ospf_spf_calculate_schedule_worker
, ospf
,
2048 delay
, &ospf
->t_spf_calc
);
2051 /* Restart OSPF SPF algorithm*/
2052 void ospf_restart_spf(struct ospf
*ospf
)
2054 if (IS_DEBUG_OSPF_EVENT
)
2055 zlog_debug("%s: Restart SPF.", __func__
);
2057 /* Handling inter area and intra area routes*/
2058 if (ospf
->new_table
) {
2059 ospf_route_delete(ospf
, ospf
->new_table
);
2060 ospf_route_table_free(ospf
->new_table
);
2061 ospf
->new_table
= route_table_init();
2064 /* Handling of TYPE-5 lsa(external routes) */
2065 if (ospf
->old_external_route
) {
2066 ospf_route_delete(ospf
, ospf
->old_external_route
);
2067 ospf_route_table_free(ospf
->old_external_route
);
2068 ospf
->old_external_route
= route_table_init();
2072 ospf_spf_calculate_schedule(ospf
, SPF_FLAG_CONFIG_CHANGE
);