1 /* OSPF SPF calculation.
2 * Copyright (C) 1999, 2000 Kunihiro Ishiguro, Toshiaki Takada
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
32 #include "sockunion.h" /* for inet_ntop () */
34 #include "ospfd/ospfd.h"
35 #include "ospfd/ospf_interface.h"
36 #include "ospfd/ospf_ism.h"
37 #include "ospfd/ospf_asbr.h"
38 #include "ospfd/ospf_lsa.h"
39 #include "ospfd/ospf_lsdb.h"
40 #include "ospfd/ospf_neighbor.h"
41 #include "ospfd/ospf_nsm.h"
42 #include "ospfd/ospf_spf.h"
43 #include "ospfd/ospf_route.h"
44 #include "ospfd/ospf_ia.h"
45 #include "ospfd/ospf_ase.h"
46 #include "ospfd/ospf_abr.h"
47 #include "ospfd/ospf_dump.h"
48 #include "ospfd/ospf_sr.h"
49 #include "ospfd/ospf_ti_lfa.h"
50 #include "ospfd/ospf_errors.h"
52 #ifdef SUPPORT_OSPF_API
53 #include "ospfd/ospf_apiserver.h"
56 /* Variables to ensure a SPF scheduled log message is printed only once */
58 static unsigned int spf_reason_flags
= 0;
60 /* dummy vertex to flag "in spftree" */
61 static const struct vertex vertex_in_spftree
= {};
62 #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
63 #define LSA_SPF_NOT_EXPLORED NULL
65 static void ospf_clear_spf_reason_flags(void)
70 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
72 spf_reason_flags
|= 1 << reason
;
75 static void ospf_vertex_free(void *);
78 * Heap related functions, for the managment of the candidates, to
79 * be used with pqueue.
81 static int vertex_cmp(const struct vertex
*v1
, const struct vertex
*v2
)
83 if (v1
->distance
!= v2
->distance
)
84 return v1
->distance
- v2
->distance
;
86 if (v1
->type
!= v2
->type
) {
88 case OSPF_VERTEX_NETWORK
:
90 case OSPF_VERTEX_ROUTER
:
96 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue
, struct vertex
, pqi
, vertex_cmp
);
98 static void lsdb_clean_stat(struct ospf_lsdb
*lsdb
)
100 struct route_table
*table
;
101 struct route_node
*rn
;
102 struct ospf_lsa
*lsa
;
105 for (i
= OSPF_MIN_LSA
; i
< OSPF_MAX_LSA
; i
++) {
106 table
= lsdb
->type
[i
].db
;
107 for (rn
= route_top(table
); rn
; rn
= route_next(rn
))
108 if ((lsa
= (rn
->info
)) != NULL
)
109 lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
113 static struct vertex_nexthop
*vertex_nexthop_new(void)
115 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
118 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
120 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
124 * Free the canonical nexthop objects for an area, ie the nexthop objects
125 * attached to the first-hop router vertices, and any intervening network
128 static void ospf_canonical_nexthops_free(struct vertex
*root
)
130 struct listnode
*node
, *nnode
;
131 struct vertex
*child
;
133 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
134 struct listnode
*n2
, *nn2
;
135 struct vertex_parent
*vp
;
138 * router vertices through an attached network each
139 * have a distinct (canonical / not inherited) nexthop
140 * which must be freed.
142 * A network vertex can only have router vertices as its
143 * children, so only one level of recursion is possible.
145 if (child
->type
== OSPF_VERTEX_NETWORK
)
146 ospf_canonical_nexthops_free(child
);
148 /* Free child nexthops pointing back to this root vertex */
149 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
)) {
150 if (vp
->parent
== root
&& vp
->nexthop
) {
151 vertex_nexthop_free(vp
->nexthop
);
153 if (vp
->local_nexthop
) {
154 vertex_nexthop_free(vp
->local_nexthop
);
155 vp
->local_nexthop
= NULL
;
163 * TODO: Parent list should be excised, in favour of maintaining only
164 * vertex_nexthop, with refcounts.
166 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
167 struct vertex_nexthop
*hop
,
168 struct vertex_nexthop
*lhop
)
170 struct vertex_parent
*new;
172 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
175 new->backlink
= backlink
;
177 new->local_nexthop
= lhop
;
182 static void vertex_parent_free(struct vertex_parent
*p
)
184 vertex_nexthop_free(p
->local_nexthop
);
185 vertex_nexthop_free(p
->nexthop
);
186 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
189 int vertex_parent_cmp(void *aa
, void *bb
)
191 struct vertex_parent
*a
= aa
, *b
= bb
;
192 return IPV4_ADDR_CMP(&a
->nexthop
->router
, &b
->nexthop
->router
);
195 static struct vertex
*ospf_vertex_new(struct ospf_area
*area
,
196 struct ospf_lsa
*lsa
)
200 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
203 new->type
= lsa
->data
->type
;
204 new->id
= lsa
->data
->id
;
205 new->lsa
= lsa
->data
;
206 new->children
= list_new();
207 new->parents
= list_new();
208 new->parents
->del
= (void (*)(void *))vertex_parent_free
;
209 new->parents
->cmp
= vertex_parent_cmp
;
214 listnode_add(area
->spf_vertex_list
, new);
216 if (IS_DEBUG_OSPF_EVENT
)
217 zlog_debug("%s: Created %s vertex %pI4", __func__
,
218 new->type
== OSPF_VERTEX_ROUTER
? "Router"
225 static void ospf_vertex_free(void *data
)
227 struct vertex
*v
= data
;
229 if (IS_DEBUG_OSPF_EVENT
)
230 zlog_debug("%s: Free %s vertex %pI4", __func__
,
231 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
235 list_delete(&v
->children
);
238 list_delete(&v
->parents
);
242 XFREE(MTYPE_OSPF_VERTEX
, v
);
245 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
246 int print_parents
, int print_children
)
248 if (!IS_DEBUG_OSPF_EVENT
)
251 zlog_debug("%s %s vertex %pI4 distance %u flags %u", msg
,
252 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
253 &v
->lsa
->id
, v
->distance
, (unsigned int)v
->flags
);
256 struct listnode
*node
;
257 struct vertex_parent
*vp
;
259 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
262 "parent %pI4 backlink %d nexthop %pI4 lsa pos %d",
263 &vp
->parent
->lsa
->id
, vp
->backlink
,
264 &vp
->nexthop
->router
,
265 vp
->nexthop
->lsa_pos
);
270 if (print_children
) {
271 struct listnode
*cnode
;
274 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
275 ospf_vertex_dump(" child:", cv
, 0, 0);
280 /* Add a vertex to the list of children in each of its parents. */
281 static void ospf_vertex_add_parent(struct vertex
*v
)
283 struct vertex_parent
*vp
;
284 struct listnode
*node
;
286 assert(v
&& v
->parents
);
288 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
289 assert(vp
->parent
&& vp
->parent
->children
);
291 /* No need to add two links from the same parent. */
292 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
293 listnode_add(vp
->parent
->children
, v
);
297 /* Find a vertex according to its router id */
298 struct vertex
*ospf_spf_vertex_find(struct in_addr id
, struct list
*vertex_list
)
300 struct listnode
*node
;
301 struct vertex
*found
;
303 for (ALL_LIST_ELEMENTS_RO(vertex_list
, node
, found
)) {
304 if (found
->id
.s_addr
== id
.s_addr
)
311 /* Find a vertex parent according to its router id */
312 struct vertex_parent
*ospf_spf_vertex_parent_find(struct in_addr id
,
313 struct vertex
*vertex
)
315 struct listnode
*node
;
316 struct vertex_parent
*found
;
318 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, found
)) {
319 if (found
->parent
->id
.s_addr
== id
.s_addr
)
326 struct vertex
*ospf_spf_vertex_by_nexthop(struct vertex
*root
,
327 struct in_addr
*nexthop
)
329 struct listnode
*node
;
330 struct vertex
*child
;
331 struct vertex_parent
*vertex_parent
;
333 for (ALL_LIST_ELEMENTS_RO(root
->children
, node
, child
)) {
334 vertex_parent
= ospf_spf_vertex_parent_find(root
->id
, child
);
335 if (vertex_parent
->nexthop
->router
.s_addr
== nexthop
->s_addr
)
342 /* Create a deep copy of a SPF vertex without children and parents */
343 static struct vertex
*ospf_spf_vertex_copy(struct vertex
*vertex
)
347 copy
= XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
349 memcpy(copy
, vertex
, sizeof(struct vertex
));
350 copy
->parents
= list_new();
351 copy
->parents
->del
= (void (*)(void *))vertex_parent_free
;
352 copy
->parents
->cmp
= vertex_parent_cmp
;
353 copy
->children
= list_new();
358 /* Create a deep copy of a SPF vertex_parent */
359 static struct vertex_parent
*
360 ospf_spf_vertex_parent_copy(struct vertex_parent
*vertex_parent
)
362 struct vertex_parent
*vertex_parent_copy
;
363 struct vertex_nexthop
*nexthop_copy
, *local_nexthop_copy
;
366 XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex_parent
));
368 nexthop_copy
= vertex_nexthop_new();
369 local_nexthop_copy
= vertex_nexthop_new();
371 memcpy(vertex_parent_copy
, vertex_parent
, sizeof(struct vertex_parent
));
372 memcpy(nexthop_copy
, vertex_parent
->nexthop
,
373 sizeof(struct vertex_nexthop
));
374 memcpy(local_nexthop_copy
, vertex_parent
->local_nexthop
,
375 sizeof(struct vertex_nexthop
));
377 vertex_parent_copy
->nexthop
= nexthop_copy
;
378 vertex_parent_copy
->local_nexthop
= local_nexthop_copy
;
380 return vertex_parent_copy
;
383 /* Create a deep copy of a SPF tree */
384 void ospf_spf_copy(struct vertex
*vertex
, struct list
*vertex_list
)
386 struct listnode
*node
;
387 struct vertex
*vertex_copy
, *child
, *child_copy
, *parent_copy
;
388 struct vertex_parent
*vertex_parent
, *vertex_parent_copy
;
390 /* First check if the node is already in the vertex list */
391 vertex_copy
= ospf_spf_vertex_find(vertex
->id
, vertex_list
);
393 vertex_copy
= ospf_spf_vertex_copy(vertex
);
394 listnode_add(vertex_list
, vertex_copy
);
397 /* Copy all parents, create parent nodes if necessary */
398 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, vertex_parent
)) {
399 parent_copy
= ospf_spf_vertex_find(vertex_parent
->parent
->id
,
403 ospf_spf_vertex_copy(vertex_parent
->parent
);
404 listnode_add(vertex_list
, parent_copy
);
406 vertex_parent_copy
= ospf_spf_vertex_parent_copy(vertex_parent
);
407 vertex_parent_copy
->parent
= parent_copy
;
408 listnode_add(vertex_copy
->parents
, vertex_parent_copy
);
411 /* Copy all children, create child nodes if necessary */
412 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
413 child_copy
= ospf_spf_vertex_find(child
->id
, vertex_list
);
415 child_copy
= ospf_spf_vertex_copy(child
);
416 listnode_add(vertex_list
, child_copy
);
418 listnode_add(vertex_copy
->children
, child_copy
);
421 /* Finally continue copying with child nodes */
422 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
))
423 ospf_spf_copy(child
, vertex_list
);
426 static void ospf_spf_remove_branch(struct vertex_parent
*vertex_parent
,
427 struct vertex
*child
,
428 struct list
*vertex_list
)
430 struct listnode
*node
, *nnode
, *inner_node
, *inner_nnode
;
431 struct vertex
*grandchild
;
432 struct vertex_parent
*vertex_parent_found
;
433 bool has_more_links
= false;
436 * First check if there are more nexthops for that parent to that child
438 for (ALL_LIST_ELEMENTS_RO(child
->parents
, node
, vertex_parent_found
)) {
439 if (vertex_parent_found
->parent
->id
.s_addr
440 == vertex_parent
->parent
->id
.s_addr
441 && vertex_parent_found
->nexthop
->router
.s_addr
442 != vertex_parent
->nexthop
->router
.s_addr
)
443 has_more_links
= true;
447 * No more links from that parent? Then delete the child from its
451 listnode_delete(vertex_parent
->parent
->children
, child
);
454 * Delete the vertex_parent from the child parents list, this needs to
457 listnode_delete(child
->parents
, vertex_parent
);
460 * Are there actually more parents left? If not, then delete the child!
461 * This is done by recursively removing the links to the grandchildren,
462 * such that finally the child can be removed without leaving unused
465 if (child
->parents
->count
== 0) {
466 for (ALL_LIST_ELEMENTS(child
->children
, node
, nnode
,
468 for (ALL_LIST_ELEMENTS(grandchild
->parents
, inner_node
,
470 vertex_parent_found
)) {
471 ospf_spf_remove_branch(vertex_parent_found
,
472 grandchild
, vertex_list
);
475 listnode_delete(vertex_list
, child
);
476 ospf_vertex_free(child
);
480 static int ospf_spf_remove_link(struct vertex
*vertex
, struct list
*vertex_list
,
481 struct router_lsa_link
*link
)
483 struct listnode
*node
, *inner_node
;
484 struct vertex
*child
;
485 struct vertex_parent
*vertex_parent
;
488 * Identify the node who shares a subnet (given by the link) with a
489 * child and remove the branch of this particular child.
491 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
492 for (ALL_LIST_ELEMENTS_RO(child
->parents
, inner_node
,
494 if ((vertex_parent
->local_nexthop
->router
.s_addr
495 & link
->link_data
.s_addr
)
496 == (link
->link_id
.s_addr
497 & link
->link_data
.s_addr
)) {
498 ospf_spf_remove_branch(vertex_parent
, child
,
505 /* No link found yet, move on recursively */
506 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
507 if (ospf_spf_remove_link(child
, vertex_list
, link
) == 0)
511 /* link was not removed yet */
515 void ospf_spf_remove_resource(struct vertex
*vertex
, struct list
*vertex_list
,
516 struct protected_resource
*resource
)
518 struct listnode
*node
, *nnode
;
519 struct vertex
*found
;
520 struct vertex_parent
*vertex_parent
;
522 switch (resource
->type
) {
523 case OSPF_TI_LFA_LINK_PROTECTION
:
524 ospf_spf_remove_link(vertex
, vertex_list
, resource
->link
);
526 case OSPF_TI_LFA_NODE_PROTECTION
:
527 found
= ospf_spf_vertex_find(resource
->router_id
, vertex_list
);
532 * Remove the node by removing all links from its parents. Note
533 * that the child is automatically removed here with the last
534 * link from a parent, hence no explicit removal of the node.
536 for (ALL_LIST_ELEMENTS(found
->parents
, node
, nnode
,
538 ospf_spf_remove_branch(vertex_parent
, found
,
548 static void ospf_spf_init(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
549 bool is_dry_run
, bool is_root_node
)
551 struct list
*vertex_list
;
554 /* Create vertex list */
555 vertex_list
= list_new();
556 vertex_list
->del
= ospf_vertex_free
;
557 area
->spf_vertex_list
= vertex_list
;
559 /* Create root node. */
560 v
= ospf_vertex_new(area
, root_lsa
);
563 area
->spf_dry_run
= is_dry_run
;
564 area
->spf_root_node
= is_root_node
;
566 /* Reset ABR and ASBR router counts. */
568 area
->asbr_count
= 0;
571 /* return index of link back to V from W, or -1 if no link found */
572 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
574 unsigned int i
, length
;
575 struct router_lsa
*rl
;
576 struct network_lsa
*nl
;
578 /* In case of W is Network LSA. */
579 if (w
->type
== OSPF_NETWORK_LSA
) {
580 if (v
->type
== OSPF_NETWORK_LSA
)
583 nl
= (struct network_lsa
*)w
;
584 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
586 for (i
= 0; i
< length
; i
++)
587 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
592 /* In case of W is Router LSA. */
593 if (w
->type
== OSPF_ROUTER_LSA
) {
594 rl
= (struct router_lsa
*)w
;
596 length
= ntohs(w
->length
);
598 for (i
= 0; i
< ntohs(rl
->links
)
599 && length
>= sizeof(struct router_lsa
);
601 switch (rl
->link
[i
].type
) {
602 case LSA_LINK_TYPE_POINTOPOINT
:
603 case LSA_LINK_TYPE_VIRTUALLINK
:
605 if (v
->type
== OSPF_ROUTER_LSA
606 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
611 case LSA_LINK_TYPE_TRANSIT
:
612 /* Network LSA ID. */
613 if (v
->type
== OSPF_NETWORK_LSA
614 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
619 case LSA_LINK_TYPE_STUB
:
620 /* Stub can't lead anywhere, carry on */
631 * Find the next link after prev_link from v to w. If prev_link is
632 * NULL, return the first link from v to w. Ignore stub and virtual links;
633 * these link types will never be returned.
635 static struct router_lsa_link
*
636 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
637 struct router_lsa_link
*prev_link
)
641 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
642 struct router_lsa_link
*l
;
644 if (w
->type
== OSPF_VERTEX_ROUTER
)
645 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
647 if (prev_link
== NULL
)
648 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
650 p
= (uint8_t *)prev_link
;
651 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
652 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
655 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
658 l
= (struct router_lsa_link
*)p
;
660 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
661 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
663 if (l
->m
[0].type
!= lsa_type
)
666 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
673 static void ospf_spf_flush_parents(struct vertex
*w
)
675 struct vertex_parent
*vp
;
676 struct listnode
*ln
, *nn
;
678 /* delete the existing nexthops */
679 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
680 list_delete_node(w
->parents
, ln
);
681 vertex_parent_free(vp
);
686 * Consider supplied next-hop for inclusion to the supplied list of
687 * equal-cost next-hops, adjust list as necessary.
689 * Returns vertex parent pointer if created otherwise `NULL` if it already
692 static struct vertex_parent
*ospf_spf_add_parent(struct vertex
*v
,
694 struct vertex_nexthop
*newhop
,
695 struct vertex_nexthop
*newlhop
,
696 unsigned int distance
)
698 struct vertex_parent
*vp
, *wp
;
699 struct listnode
*node
;
701 /* we must have a newhop, and a distance */
702 assert(v
&& w
&& newhop
);
706 * IFF w has already been assigned a distance, then we shouldn't get
707 * here unless callers have determined V(l)->W is shortest /
708 * equal-shortest path (0 is a special case distance (no distance yet
712 assert(distance
<= w
->distance
);
714 w
->distance
= distance
;
716 if (IS_DEBUG_OSPF_EVENT
)
717 zlog_debug("%s: Adding %pI4 as parent of %pI4", __func__
,
718 &v
->lsa
->id
, &w
->lsa
->id
);
721 * Adding parent for a new, better path: flush existing parents from W.
723 if (distance
< w
->distance
) {
724 if (IS_DEBUG_OSPF_EVENT
)
726 "%s: distance %d better than %d, flushing existing parents",
727 __func__
, distance
, w
->distance
);
728 ospf_spf_flush_parents(w
);
729 w
->distance
= distance
;
733 * new parent is <= existing parents, add it to parent list (if nexthop
734 * not on parent list)
736 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
737 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
738 if (IS_DEBUG_OSPF_EVENT
)
740 "%s: ... nexthop already on parent list, skipping add",
747 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
,
749 listnode_add_sort(w
->parents
, vp
);
754 static int match_stub_prefix(struct lsa_header
*lsa
, struct in_addr v_link_addr
,
755 struct in_addr w_link_addr
)
758 struct router_lsa_link
*l
= NULL
;
759 struct in_addr masked_lsa_addr
;
761 if (lsa
->type
!= OSPF_ROUTER_LSA
)
764 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
765 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
768 l
= (struct router_lsa_link
*)p
;
769 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
770 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
772 if (l
->m
[0].type
!= LSA_LINK_TYPE_STUB
)
775 masked_lsa_addr
.s_addr
=
776 (l
->link_id
.s_addr
& l
->link_data
.s_addr
);
778 /* check that both links belong to the same stub subnet */
779 if ((masked_lsa_addr
.s_addr
780 == (v_link_addr
.s_addr
& l
->link_data
.s_addr
))
781 && (masked_lsa_addr
.s_addr
782 == (w_link_addr
.s_addr
& l
->link_data
.s_addr
)))
790 * 16.1.1. Calculate nexthop from root through V (parent) to
791 * vertex W (destination), with given distance from root->W.
793 * The link must be supplied if V is the root vertex. In all other cases
796 * Note that this function may fail, hence the state of the destination
797 * vertex, W, should /not/ be modified in a dependent manner until
798 * this function returns. This function will update the W vertex with the
799 * provided distance as appropriate.
801 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
802 struct vertex
*v
, struct vertex
*w
,
803 struct router_lsa_link
*l
,
804 unsigned int distance
, int lsa_pos
)
806 struct listnode
*node
, *nnode
;
807 struct vertex_nexthop
*nh
, *lnh
;
808 struct vertex_parent
*vp
;
809 unsigned int added
= 0;
811 if (IS_DEBUG_OSPF_EVENT
) {
812 zlog_debug("%s: Start", __func__
);
813 ospf_vertex_dump("V (parent):", v
, 1, 1);
814 ospf_vertex_dump("W (dest) :", w
, 1, 1);
815 zlog_debug("V->W distance: %d", distance
);
818 if (v
== area
->spf
) {
820 * 16.1.1 para 4. In the first case, the parent vertex (V) is
821 * the root (the calculating router itself). This means that
822 * the destination is either a directly connected network or
823 * directly connected router. The outgoing interface in this
824 * case is simply the OSPF interface connecting to the
825 * destination network/router.
828 /* we *must* be supplied with the link data */
831 if (IS_DEBUG_OSPF_EVENT
)
833 "%s: considering link type:%d link_id:%pI4 link_data:%pI4",
834 __func__
, l
->m
[0].type
, &l
->link_id
,
837 if (w
->type
== OSPF_VERTEX_ROUTER
) {
839 * l is a link from v to w l2 will be link from w to v
841 struct router_lsa_link
*l2
= NULL
;
843 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
844 struct ospf_interface
*oi
= NULL
;
845 struct in_addr nexthop
= {.s_addr
= 0};
847 if (area
->spf_root_node
) {
848 oi
= ospf_if_lookup_by_lsa_pos(area
,
852 "%s: OI not found in LSA: lsa_pos: %d link_id:%pI4 link_data:%pI4",
861 * If the destination is a router which connects
862 * to the calculating router via a
863 * Point-to-MultiPoint network, the
864 * destination's next hop IP address(es) can be
865 * determined by examining the destination's
866 * router-LSA: each link pointing back to the
867 * calculating router and having a Link Data
868 * field belonging to the Point-to-MultiPoint
869 * network provides an IP address of the next
872 * At this point l is a link from V to W, and V
873 * is the root ("us"). If it is a point-to-
874 * multipoint interface, then look through the
875 * links in the opposite direction (W to V).
876 * If any of them have an address that lands
877 * within the subnet declared by the PtMP link,
878 * then that link is a constituent of the PtMP
879 * link, and its address is a nexthop address
882 * Note for point-to-point interfaces:
884 * Having nexthop = 0 (as proposed in the RFC)
885 * is tempting, but NOT acceptable. It breaks
886 * AS-External routes with a forwarding address,
887 * since ospf_ase_complete_direct_routes() will
888 * mistakenly assume we've reached the last hop
889 * and should place the forwarding address as
890 * nexthop. Also, users may configure multi-
891 * access links in p2p mode, so we need the IP
892 * to ARP the nexthop.
894 * If the calculating router is the SPF root
895 * node and the link is P2P then access the
896 * interface information directly. This can be
897 * crucial when e.g. IP unnumbered is used
898 * where 'correct' nexthop information are not
899 * available via Router LSAs.
901 * Otherwise handle P2P and P2MP the same way
902 * as described above using a reverse lookup to
903 * figure out the nexthop.
907 * HACK: we don't know (yet) how to distinguish
908 * between P2P and P2MP interfaces by just
909 * looking at LSAs, which is important for
910 * TI-LFA since you want to do SPF calculations
911 * from the perspective of other nodes. Since
912 * TI-LFA is currently not implemented for P2MP
913 * we just check here if it is enabled and then
914 * blindly assume that P2P is used. Ultimately
915 * the interface code needs to be removed
918 if (area
->ospf
->ti_lfa_enabled
919 || (oi
&& oi
->type
== OSPF_IFTYPE_POINTOPOINT
)
920 || (oi
&& oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
921 && oi
->address
->prefixlen
== IPV4_MAX_BITLEN
)) {
922 struct ospf_neighbor
*nbr_w
= NULL
;
924 /* Calculating node is root node, link
926 if (area
->spf_root_node
) {
927 nbr_w
= ospf_nbr_lookup_by_routerid(
928 oi
->nbrs
, &l
->link_id
);
931 nexthop
= nbr_w
->src
;
937 while ((l2
= ospf_get_next_link(
939 if (match_stub_prefix(
950 } else if (oi
&& oi
->type
951 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
952 struct prefix_ipv4 la
;
955 la
.prefixlen
= oi
->address
->prefixlen
;
958 * V links to W on PtMP interface;
959 * find the interface address on W
961 while ((l2
= ospf_get_next_link(w
, v
,
963 la
.prefix
= l2
->link_data
;
965 if (prefix_cmp((struct prefix
971 nexthop
= l2
->link_data
;
977 nh
= vertex_nexthop_new();
978 nh
->router
= nexthop
;
979 nh
->lsa_pos
= lsa_pos
;
982 * Since v is the root the nexthop and
983 * local nexthop are the same.
985 lnh
= vertex_nexthop_new();
987 sizeof(struct vertex_nexthop
));
989 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
992 vertex_nexthop_free(nh
);
993 vertex_nexthop_free(lnh
);
998 "%s: could not determine nexthop for link %s",
999 __func__
, oi
? oi
->ifp
->name
: "");
1000 } /* end point-to-point link from V to W */
1001 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
1003 * VLink implementation limitations:
1004 * a) vl_data can only reference one nexthop,
1005 * so no ECMP to backbone through VLinks.
1006 * Though transit-area summaries may be
1007 * considered, and those can be ECMP.
1008 * b) We can only use /one/ VLink, even if
1009 * multiple ones exist this router through
1010 * multiple transit-areas.
1013 struct ospf_vl_data
*vl_data
;
1015 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
1019 && CHECK_FLAG(vl_data
->flags
,
1020 OSPF_VL_FLAG_APPROVED
)) {
1021 nh
= vertex_nexthop_new();
1022 nh
->router
= vl_data
->nexthop
.router
;
1023 nh
->lsa_pos
= vl_data
->nexthop
.lsa_pos
;
1026 * Since v is the root the nexthop and
1027 * local nexthop are the same.
1029 lnh
= vertex_nexthop_new();
1031 sizeof(struct vertex_nexthop
));
1033 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
1036 vertex_nexthop_free(nh
);
1037 vertex_nexthop_free(lnh
);
1043 "%s: vl_data for VL link not found",
1045 } /* end virtual-link from V to W */
1047 } /* end W is a Router vertex */
1049 assert(w
->type
== OSPF_VERTEX_NETWORK
);
1051 nh
= vertex_nexthop_new();
1052 nh
->router
.s_addr
= 0; /* Nexthop not required */
1053 nh
->lsa_pos
= lsa_pos
;
1056 * Since v is the root the nexthop and
1057 * local nexthop are the same.
1059 lnh
= vertex_nexthop_new();
1060 memcpy(lnh
, nh
, sizeof(struct vertex_nexthop
));
1062 if (ospf_spf_add_parent(v
, w
, nh
, lnh
, distance
) ==
1064 vertex_nexthop_free(nh
);
1065 vertex_nexthop_free(lnh
);
1070 } /* end V is the root */
1071 /* Check if W's parent is a network connected to root. */
1072 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
1073 /* See if any of V's parents are the root. */
1074 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1075 if (vp
->parent
== area
->spf
) {
1077 * 16.1.1 para 5. ...the parent vertex is a
1078 * network that directly connects the
1079 * calculating router to the destination
1080 * router. The list of next hops is then
1081 * determined by examining the destination's
1085 assert(w
->type
== OSPF_VERTEX_ROUTER
);
1086 while ((l
= ospf_get_next_link(w
, v
, l
))) {
1088 * ... For each link in the router-LSA
1089 * that points back to the parent
1090 * network, the link's Link Data field
1091 * provides the IP address of a next hop
1092 * router. The outgoing interface to use
1093 * can then be derived from the next
1094 * hop IP address (or it can be
1095 * inherited from the parent network).
1097 nh
= vertex_nexthop_new();
1098 nh
->router
= l
->link_data
;
1099 nh
->lsa_pos
= vp
->nexthop
->lsa_pos
;
1102 * Since v is the root the nexthop and
1103 * local nexthop are the same.
1105 lnh
= vertex_nexthop_new();
1107 sizeof(struct vertex_nexthop
));
1110 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
1113 vertex_nexthop_free(nh
);
1114 vertex_nexthop_free(lnh
);
1118 * Note lack of return is deliberate. See next
1124 * NB: This code is non-trivial.
1126 * E.g. it is not enough to know that V connects to the root. It
1127 * is also important that the while above, looping through all
1128 * links from W->V found at least one link, so that we know
1129 * there is bi-directional connectivity between V and W (which
1130 * need not be the case, e.g. when OSPF has not yet converged
1131 * fully). Otherwise, if we /always/ return here, without having
1132 * checked that root->V->-W actually resulted in a valid nexthop
1133 * being created, then we we will prevent SPF from finding/using
1134 * higher cost paths.
1136 * It is important, if root->V->W has not been added, that we
1137 * continue through to the intervening-router nexthop code
1138 * below. So as to ensure other paths to V may be used. This
1139 * avoids unnecessary blackholes while OSPF is converging.
1141 * I.e. we may have arrived at this function, examining V -> W,
1142 * via workable paths other than root -> V, and it's important
1143 * to avoid getting "confused" by non-working root->V->W path
1144 * - it's important to *not* lose the working non-root paths,
1145 * just because of a non-viable root->V->W.
1152 * 16.1.1 para 4. If there is at least one intervening router in the
1153 * current shortest path between the destination and the root, the
1154 * destination simply inherits the set of next hops from the
1157 if (IS_DEBUG_OSPF_EVENT
)
1158 zlog_debug("%s: Intervening routers, adding parent(s)",
1161 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1165 * The nexthop is inherited, but the local nexthop still needs
1169 lnh
= vertex_nexthop_new();
1170 lnh
->router
= l
->link_data
;
1171 lnh
->lsa_pos
= lsa_pos
;
1176 nh
= vertex_nexthop_new();
1179 if (ospf_spf_add_parent(v
, w
, nh
, lnh
, distance
) == NULL
) {
1180 vertex_nexthop_free(nh
);
1181 vertex_nexthop_free(lnh
);
1188 static int ospf_spf_is_protected_resource(struct ospf_area
*area
,
1189 struct router_lsa_link
*link
,
1190 struct lsa_header
*lsa
)
1193 struct router_lsa_link
*p_link
;
1194 struct router_lsa_link
*l
= NULL
;
1195 struct in_addr router_id
;
1198 if (!area
->spf_protected_resource
)
1201 link_type
= link
->m
[0].type
;
1203 switch (area
->spf_protected_resource
->type
) {
1204 case OSPF_TI_LFA_LINK_PROTECTION
:
1205 p_link
= area
->spf_protected_resource
->link
;
1209 /* For P2P: check if the link belongs to the same subnet */
1210 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1211 && (p_link
->link_id
.s_addr
& p_link
->link_data
.s_addr
)
1212 == (link
->link_data
.s_addr
1213 & p_link
->link_data
.s_addr
))
1216 /* For stub: check if this the same subnet */
1217 if (link_type
== LSA_LINK_TYPE_STUB
1218 && (p_link
->link_id
.s_addr
== link
->link_id
.s_addr
)
1219 && (p_link
->link_data
.s_addr
== link
->link_data
.s_addr
))
1223 case OSPF_TI_LFA_NODE_PROTECTION
:
1224 router_id
= area
->spf_protected_resource
->router_id
;
1225 if (router_id
.s_addr
== INADDR_ANY
)
1228 /* For P2P: check if the link leads to the protected node */
1229 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1230 && link
->link_id
.s_addr
== router_id
.s_addr
)
1233 /* The rest is about stub links! */
1234 if (link_type
!= LSA_LINK_TYPE_STUB
)
1238 * Check if there's a P2P link in the router LSA with the
1239 * corresponding link data in the same subnet.
1242 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1243 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
1246 l
= (struct router_lsa_link
*)p
;
1247 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1248 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1250 /* We only care about P2P with the proper link id */
1251 if ((l
->m
[0].type
!= LSA_LINK_TYPE_POINTOPOINT
)
1252 || (l
->link_id
.s_addr
!= router_id
.s_addr
))
1255 /* Link data in the subnet given by the link? */
1256 if ((link
->link_id
.s_addr
& link
->link_data
.s_addr
)
1257 == (l
->link_data
.s_addr
& link
->link_data
.s_addr
))
1262 case OSPF_TI_LFA_UNDEFINED_PROTECTION
:
1270 * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
1271 * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
1272 * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
1273 * corresponding link in the LSA of W and extract the particular weight.
1275 * TODO: Only P2P supported by now!
1277 static uint16_t get_reverse_distance(struct vertex
*v
,
1278 struct router_lsa_link
*l
,
1279 struct ospf_lsa
*w_lsa
)
1282 struct router_lsa_link
*w_link
;
1283 uint16_t distance
= 0;
1285 assert(w_lsa
&& w_lsa
->data
);
1287 p
= ((uint8_t *)w_lsa
->data
) + OSPF_LSA_HEADER_SIZE
+ 4;
1288 lim
= ((uint8_t *)w_lsa
->data
) + ntohs(w_lsa
->data
->length
);
1291 w_link
= (struct router_lsa_link
*)p
;
1292 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1293 + (w_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1295 /* Only care about P2P with link ID equal to V's router id */
1296 if (w_link
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
1297 && w_link
->link_id
.s_addr
== v
->id
.s_addr
) {
1298 distance
= ntohs(w_link
->m
[0].metric
);
1304 * This might happen if the LSA for W is not complete yet. In this
1305 * case we take the weight of the 'forward' link from V. When the LSA
1306 * for W is completed the reverse SPF is run again anyway.
1309 distance
= ntohs(l
->m
[0].metric
);
1311 if (IS_DEBUG_OSPF_EVENT
)
1312 zlog_debug("%s: reversed distance is %u", __func__
, distance
);
1319 * v is on the SPF tree. Examine the links in v's LSA. Update the list of
1320 * candidates with any vertices not already on the list. If a lower-cost path
1321 * is found to a vertex already on the candidate list, store the new cost.
1323 static void ospf_spf_next(struct vertex
*v
, struct ospf_area
*area
,
1324 struct vertex_pqueue_head
*candidate
)
1326 struct ospf_lsa
*w_lsa
= NULL
;
1329 struct router_lsa_link
*l
= NULL
;
1331 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
1332 uint16_t link_distance
;
1335 * If this is a router-LSA, and bit V of the router-LSA (see Section
1336 * A.4.2:RFC2328) is set, set Area A's TransitCapability to true.
1338 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1339 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
1340 area
->transit
= OSPF_TRANSIT_TRUE
;
1343 if (IS_DEBUG_OSPF_EVENT
)
1344 zlog_debug("%s: Next vertex of %s vertex %pI4", __func__
,
1345 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
1348 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1349 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1353 unsigned int distance
;
1355 /* In case of V is Router-LSA. */
1356 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
1357 l
= (struct router_lsa_link
*)p
;
1359 lsa_pos
= lsa_pos_next
; /* LSA link position */
1362 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1363 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1366 * (a) If this is a link to a stub network, examine the
1367 * next link in V's LSA. Links to stub networks will
1368 * be considered in the second stage of the shortest
1371 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
1375 * Don't process TI-LFA protected resources.
1377 * TODO: Replace this by a proper solution, e.g. remove
1378 * corresponding links from the LSDB and run the SPF
1379 * algo with the stripped-down LSDB.
1381 if (ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1385 * (b) Otherwise, W is a transit vertex (router or
1386 * transit network). Look up the vertex W's LSA
1387 * (router-LSA or network-LSA) in Area A's link state
1391 case LSA_LINK_TYPE_POINTOPOINT
:
1392 case LSA_LINK_TYPE_VIRTUALLINK
:
1393 if (type
== LSA_LINK_TYPE_VIRTUALLINK
1394 && IS_DEBUG_OSPF_EVENT
)
1396 "looking up LSA through VL: %pI4",
1398 w_lsa
= ospf_lsa_lookup(area
->ospf
, area
,
1400 l
->link_id
, l
->link_id
);
1401 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1402 zlog_debug("found Router LSA %pI4",
1405 case LSA_LINK_TYPE_TRANSIT
:
1406 if (IS_DEBUG_OSPF_EVENT
)
1408 "Looking up Network LSA, ID: %pI4",
1410 w_lsa
= ospf_lsa_lookup_by_id(
1411 area
, OSPF_NETWORK_LSA
, l
->link_id
);
1412 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1413 zlog_debug("found the LSA");
1416 flog_warn(EC_OSPF_LSA
,
1417 "Invalid LSA link type %d", type
);
1422 * For TI-LFA we might need the reverse SPF.
1423 * Currently only works with P2P!
1425 if (type
== LSA_LINK_TYPE_POINTOPOINT
1426 && area
->spf_reversed
)
1428 get_reverse_distance(v
, l
, w_lsa
);
1430 link_distance
= ntohs(l
->m
[0].metric
);
1432 /* step (d) below */
1433 distance
= v
->distance
+ link_distance
;
1435 /* In case of V is Network-LSA. */
1436 r
= (struct in_addr
*)p
;
1437 p
+= sizeof(struct in_addr
);
1439 /* Lookup the vertex W's LSA. */
1440 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
1442 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1443 zlog_debug("found Router LSA %pI4",
1446 /* step (d) below */
1447 distance
= v
->distance
;
1451 * (b cont.) If the LSA does not exist, or its LS age is equal
1452 * to MaxAge, or it does not have a link back to vertex V,
1453 * examine the next link in V's LSA.[23]
1455 if (w_lsa
== NULL
) {
1456 if (IS_DEBUG_OSPF_EVENT
)
1457 zlog_debug("No LSA found");
1461 if (IS_LSA_MAXAGE(w_lsa
)) {
1462 if (IS_DEBUG_OSPF_EVENT
)
1463 zlog_debug("LSA is MaxAge");
1467 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
1468 if (IS_DEBUG_OSPF_EVENT
)
1469 zlog_debug("The LSA doesn't have a link back");
1474 * (c) If vertex W is already on the shortest-path tree, examine
1475 * the next link in the LSA.
1477 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
1478 if (IS_DEBUG_OSPF_EVENT
)
1479 zlog_debug("The LSA is already in SPF");
1484 * (d) Calculate the link state cost D of the resulting path
1485 * from the root to vertex W. D is equal to the sum of the link
1486 * state cost of the (already calculated) shortest path to
1487 * vertex V and the advertised cost of the link between vertices
1491 /* calculate link cost D -- moved above */
1493 /* Is there already vertex W in candidate list? */
1494 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
1495 /* prepare vertex W. */
1496 w
= ospf_vertex_new(area
, w_lsa
);
1498 /* Calculate nexthop to W. */
1499 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
1501 vertex_pqueue_add(candidate
, w
);
1503 listnode_delete(area
->spf_vertex_list
, w
);
1504 ospf_vertex_free(w
);
1505 w_lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
1506 if (IS_DEBUG_OSPF_EVENT
)
1507 zlog_debug("Nexthop Calc failed");
1509 } else if (w_lsa
->stat
!= LSA_SPF_IN_SPFTREE
) {
1511 if (w
->distance
< distance
) {
1514 else if (w
->distance
== distance
) {
1516 * Found an equal-cost path to W.
1517 * Calculate nexthop of to W from V.
1519 ospf_nexthop_calculation(area
, v
, w
, l
,
1524 * Found a lower-cost path to W.
1525 * nexthop_calculation is conditional, if it
1526 * finds valid nexthop it will call
1527 * spf_add_parents, which will flush the old
1530 vertex_pqueue_del(candidate
, w
);
1531 ospf_nexthop_calculation(area
, v
, w
, l
,
1533 vertex_pqueue_add(candidate
, w
);
1535 } /* end W is already on the candidate list */
1536 } /* end loop over the links in V's LSA */
1539 static void ospf_spf_dump(struct vertex
*v
, int i
)
1541 struct listnode
*cnode
;
1542 struct listnode
*nnode
;
1543 struct vertex_parent
*parent
;
1545 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1546 if (IS_DEBUG_OSPF_EVENT
)
1547 zlog_debug("SPF Result: %d [R] %pI4", i
,
1550 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1551 if (IS_DEBUG_OSPF_EVENT
)
1552 zlog_debug("SPF Result: %d [N] %pI4/%d", i
,
1554 ip_masklen(lsa
->mask
));
1557 if (IS_DEBUG_OSPF_EVENT
)
1558 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1559 zlog_debug(" nexthop %p %pI4 %d",
1560 (void *)parent
->nexthop
,
1561 &parent
->nexthop
->router
,
1562 parent
->nexthop
->lsa_pos
);
1567 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1568 ospf_spf_dump(v
, i
);
1571 void ospf_spf_print(struct vty
*vty
, struct vertex
*v
, int i
)
1573 struct listnode
*cnode
;
1574 struct listnode
*nnode
;
1575 struct vertex_parent
*parent
;
1577 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1578 vty_out(vty
, "SPF Result: depth %d [R] %pI4\n", i
, &v
->lsa
->id
);
1580 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1581 vty_out(vty
, "SPF Result: depth %d [N] %pI4/%d\n", i
,
1582 &v
->lsa
->id
, ip_masklen(lsa
->mask
));
1585 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1587 " nexthop %pI4 lsa pos %d -- local nexthop %pI4 lsa pos %d\n",
1588 &parent
->nexthop
->router
, parent
->nexthop
->lsa_pos
,
1589 &parent
->local_nexthop
->router
,
1590 parent
->local_nexthop
->lsa_pos
);
1595 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1596 ospf_spf_print(vty
, v
, i
);
1599 /* Second stage of SPF calculation. */
1600 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1601 struct route_table
*rt
, int parent_is_root
)
1603 struct listnode
*cnode
, *cnnode
;
1604 struct vertex
*child
;
1606 if (IS_DEBUG_OSPF_EVENT
)
1607 zlog_debug("%s: processing stubs for area %pI4", __func__
,
1610 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1613 struct router_lsa_link
*l
;
1614 struct router_lsa
*router_lsa
;
1617 if (IS_DEBUG_OSPF_EVENT
)
1618 zlog_debug("%s: processing router LSA, id: %pI4",
1619 __func__
, &v
->lsa
->id
);
1621 router_lsa
= (struct router_lsa
*)v
->lsa
;
1623 if (IS_DEBUG_OSPF_EVENT
)
1624 zlog_debug("%s: we have %d links to process", __func__
,
1625 ntohs(router_lsa
->links
));
1627 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1628 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1631 l
= (struct router_lsa_link
*)p
;
1633 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1634 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1636 /* Don't process TI-LFA protected resources */
1637 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
1638 && !ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1639 ospf_intra_add_stub(rt
, l
, v
, area
,
1640 parent_is_root
, lsa_pos
);
1645 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1648 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1649 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1653 * The first level of routers connected to the root
1654 * should have 'parent_is_root' set, including those
1655 * connected via a network vertex.
1659 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1662 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1664 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1668 void ospf_rtrs_free(struct route_table
*rtrs
)
1670 struct route_node
*rn
;
1671 struct list
*or_list
;
1672 struct ospf_route
* or ;
1673 struct listnode
*node
, *nnode
;
1675 if (IS_DEBUG_OSPF_EVENT
)
1676 zlog_debug("Route: Router Routing Table free");
1678 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1679 if ((or_list
= rn
->info
) != NULL
) {
1680 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1681 ospf_route_free(or);
1683 list_delete(&or_list
);
1685 /* Unlock the node. */
1687 route_unlock_node(rn
);
1690 route_table_finish(rtrs
);
1693 void ospf_spf_cleanup(struct vertex
*spf
, struct list
*vertex_list
)
1696 * Free nexthop information, canonical versions of which are
1697 * attached the first level of router vertices attached to the
1698 * root vertex, see ospf_nexthop_calculation.
1701 ospf_canonical_nexthops_free(spf
);
1703 /* Free SPF vertices list with deconstructor ospf_vertex_free. */
1705 list_delete(&vertex_list
);
1708 /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */
1709 void ospf_spf_calculate(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
1710 struct route_table
*new_table
,
1711 struct route_table
*all_rtrs
,
1712 struct route_table
*new_rtrs
, bool is_dry_run
,
1715 struct vertex_pqueue_head candidate
;
1718 if (IS_DEBUG_OSPF_EVENT
) {
1719 zlog_debug("%s: Start: running Dijkstra for area %pI4",
1720 __func__
, &area
->area_id
);
1724 * If the router LSA of the root is not yet allocated, return this
1725 * area's calculation. In the 'usual' case the root_lsa is the
1726 * self-originated router LSA of the node itself.
1729 if (IS_DEBUG_OSPF_EVENT
)
1731 "%s: Skip area %pI4's calculation due to empty root LSA",
1732 __func__
, &area
->area_id
);
1736 /* Initialize the algorithm's data structures, see RFC2328 16.1. (1). */
1739 * This function scans all the LSA database and set the stat field to
1740 * LSA_SPF_NOT_EXPLORED.
1742 lsdb_clean_stat(area
->lsdb
);
1744 /* Create a new heap for the candidates. */
1745 vertex_pqueue_init(&candidate
);
1748 * Initialize the shortest-path tree to only the root (which is usually
1749 * the router doing the calculation).
1751 ospf_spf_init(area
, root_lsa
, is_dry_run
, is_root_node
);
1753 /* Set Area A's TransitCapability to false. */
1754 area
->transit
= OSPF_TRANSIT_FALSE
;
1755 area
->shortcut_capability
= 1;
1758 * Use the root vertex for the start of the SPF algorithm and make it
1762 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1765 /* RFC2328 16.1. (2). */
1766 ospf_spf_next(v
, area
, &candidate
);
1768 /* RFC2328 16.1. (3). */
1769 v
= vertex_pqueue_pop(&candidate
);
1771 /* No more vertices left. */
1774 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1776 ospf_vertex_add_parent(v
);
1778 /* RFC2328 16.1. (4). */
1779 if (v
->type
!= OSPF_VERTEX_ROUTER
)
1780 ospf_intra_add_transit(new_table
, v
, area
);
1782 ospf_intra_add_router(new_rtrs
, v
, area
, false);
1784 ospf_intra_add_router(all_rtrs
, v
, area
, true);
1787 /* Iterate back to (2), see RFC2328 16.1. (5). */
1790 if (IS_DEBUG_OSPF_EVENT
) {
1791 ospf_spf_dump(area
->spf
, 0);
1792 ospf_route_table_dump(new_table
);
1794 ospf_router_route_table_dump(all_rtrs
);
1798 * Second stage of SPF calculation procedure's, add leaves to the tree
1799 * for stub networks.
1801 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1803 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1805 /* Increment SPF Calculation Counter. */
1806 area
->spf_calculation
++;
1808 monotime(&area
->ospf
->ts_spf
);
1809 area
->ts_spf
= area
->ospf
->ts_spf
;
1811 if (IS_DEBUG_OSPF_EVENT
)
1812 zlog_debug("%s: Stop. %zd vertices", __func__
,
1813 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1816 void ospf_spf_calculate_area(struct ospf
*ospf
, struct ospf_area
*area
,
1817 struct route_table
*new_table
,
1818 struct route_table
*all_rtrs
,
1819 struct route_table
*new_rtrs
)
1821 ospf_spf_calculate(area
, area
->router_lsa_self
, new_table
, all_rtrs
,
1822 new_rtrs
, false, true);
1824 if (ospf
->ti_lfa_enabled
)
1825 ospf_ti_lfa_compute(area
, new_table
,
1826 ospf
->ti_lfa_protection_type
);
1828 ospf_spf_cleanup(area
->spf
, area
->spf_vertex_list
);
1831 area
->spf_vertex_list
= NULL
;
1834 void ospf_spf_calculate_areas(struct ospf
*ospf
, struct route_table
*new_table
,
1835 struct route_table
*all_rtrs
,
1836 struct route_table
*new_rtrs
)
1838 struct ospf_area
*area
;
1839 struct listnode
*node
, *nnode
;
1841 /* Calculate SPF for each area. */
1842 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1843 /* Do backbone last, so as to first discover intra-area paths
1844 * for any back-bone virtual-links */
1845 if (ospf
->backbone
&& ospf
->backbone
== area
)
1848 ospf_spf_calculate_area(ospf
, area
, new_table
, all_rtrs
,
1852 /* SPF for backbone, if required */
1854 ospf_spf_calculate_area(ospf
, ospf
->backbone
, new_table
,
1855 all_rtrs
, new_rtrs
);
1858 /* Worker for SPF calculation scheduler. */
1859 static void ospf_spf_calculate_schedule_worker(struct thread
*thread
)
1861 struct ospf
*ospf
= THREAD_ARG(thread
);
1862 struct route_table
*new_table
, *new_rtrs
;
1863 struct route_table
*all_rtrs
= NULL
;
1864 struct timeval start_time
, spf_start_time
;
1865 unsigned long ia_time
, prune_time
, rt_time
;
1866 unsigned long abr_time
, total_spf_time
, spf_time
;
1867 char rbuf
[32]; /* reason_buf */
1869 if (IS_DEBUG_OSPF_EVENT
)
1870 zlog_debug("SPF: Timer (SPF calculation expire)");
1872 ospf
->t_spf_calc
= NULL
;
1874 ospf_vl_unapprove(ospf
);
1876 /* Execute SPF for each area including backbone, see RFC 2328 16.1. */
1877 monotime(&spf_start_time
);
1878 new_table
= route_table_init(); /* routing table */
1879 new_rtrs
= route_table_init(); /* ABR/ASBR routing table */
1881 /* If we have opaque enabled then track all router reachability */
1882 if (CHECK_FLAG(ospf
->opaque
, OPAQUE_OPERATION_READY_BIT
))
1883 all_rtrs
= route_table_init();
1885 ospf_spf_calculate_areas(ospf
, new_table
, all_rtrs
, new_rtrs
);
1886 spf_time
= monotime_since(&spf_start_time
, NULL
);
1888 ospf_vl_shut_unapproved(ospf
);
1890 /* Calculate inter-area routes, see RFC 2328 16.2. */
1891 monotime(&start_time
);
1892 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1893 ia_time
= monotime_since(&start_time
, NULL
);
1895 /* Get rid of transit networks and routers we cannot reach anyway. */
1896 monotime(&start_time
);
1897 ospf_prune_unreachable_networks(new_table
);
1899 ospf_prune_unreachable_routers(all_rtrs
);
1900 ospf_prune_unreachable_routers(new_rtrs
);
1901 prune_time
= monotime_since(&start_time
, NULL
);
1903 /* Note: RFC 2328 16.3. is apparently missing. */
1906 * Calculate AS external routes, see RFC 2328 16.4.
1907 * There is a dedicated routing table for external routes which is not
1908 * handled here directly
1910 ospf_ase_calculate_schedule(ospf
);
1911 ospf_ase_calculate_timer_add(ospf
);
1913 if (IS_DEBUG_OSPF_EVENT
)
1915 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1916 __func__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1917 ospf
->vrf_id
, new_table
->count
);
1919 /* Update routing table. */
1920 monotime(&start_time
);
1921 ospf_route_install(ospf
, new_table
);
1922 rt_time
= monotime_since(&start_time
, NULL
);
1924 /* Free old all routers routing table */
1925 if (ospf
->oall_rtrs
) {
1926 ospf_rtrs_free(ospf
->oall_rtrs
);
1927 ospf
->oall_rtrs
= NULL
;
1930 /* Update all routers routing table */
1931 ospf
->oall_rtrs
= ospf
->all_rtrs
;
1932 ospf
->all_rtrs
= all_rtrs
;
1933 #ifdef SUPPORT_OSPF_API
1934 ospf_apiserver_notify_reachable(ospf
->oall_rtrs
, ospf
->all_rtrs
);
1937 /* Free old ABR/ASBR routing table */
1938 if (ospf
->old_rtrs
) {
1939 ospf_rtrs_free(ospf
->old_rtrs
);
1940 ospf
->old_rtrs
= NULL
;
1943 /* Update ABR/ASBR routing table */
1944 ospf
->old_rtrs
= ospf
->new_rtrs
;
1945 ospf
->new_rtrs
= new_rtrs
;
1947 /* ABRs may require additional changes, see RFC 2328 16.7. */
1948 monotime(&start_time
);
1949 if (IS_OSPF_ABR(ospf
)) {
1951 ospf_abr_nssa_check_status(ospf
);
1952 ospf_abr_task(ospf
);
1954 abr_time
= monotime_since(&start_time
, NULL
);
1956 /* Schedule Segment Routing update */
1957 ospf_sr_update_task(ospf
);
1960 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1963 if (spf_reason_flags
) {
1964 if (spf_reason_flags
& (1 << SPF_FLAG_ROUTER_LSA_INSTALL
))
1965 strlcat(rbuf
, "R, ", sizeof(rbuf
));
1966 if (spf_reason_flags
& (1 << SPF_FLAG_NETWORK_LSA_INSTALL
))
1967 strlcat(rbuf
, "N, ", sizeof(rbuf
));
1968 if (spf_reason_flags
& (1 << SPF_FLAG_SUMMARY_LSA_INSTALL
))
1969 strlcat(rbuf
, "S, ", sizeof(rbuf
));
1970 if (spf_reason_flags
& (1 << SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
))
1971 strlcat(rbuf
, "AS, ", sizeof(rbuf
));
1972 if (spf_reason_flags
& (1 << SPF_FLAG_ABR_STATUS_CHANGE
))
1973 strlcat(rbuf
, "ABR, ", sizeof(rbuf
));
1974 if (spf_reason_flags
& (1 << SPF_FLAG_ASBR_STATUS_CHANGE
))
1975 strlcat(rbuf
, "ASBR, ", sizeof(rbuf
));
1976 if (spf_reason_flags
& (1 << SPF_FLAG_MAXAGE
))
1977 strlcat(rbuf
, "M, ", sizeof(rbuf
));
1978 if (spf_reason_flags
& (1 << SPF_FLAG_GR_FINISH
))
1979 strlcat(rbuf
, "GR, ", sizeof(rbuf
));
1981 size_t rbuflen
= strlen(rbuf
);
1983 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1988 if (IS_DEBUG_OSPF_EVENT
) {
1989 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1990 zlog_info(" SPF Time: %ld", spf_time
);
1991 zlog_info(" InterArea: %ld", ia_time
);
1992 zlog_info(" Prune: %ld", prune_time
);
1993 zlog_info(" RouteInstall: %ld", rt_time
);
1994 if (IS_OSPF_ABR(ospf
))
1995 zlog_info(" ABR: %ld (%d areas)",
1996 abr_time
, ospf
->areas
->count
);
1997 zlog_info("Reason(s) for SPF: %s", rbuf
);
2000 ospf_clear_spf_reason_flags();
2004 * Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer
2007 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
2009 unsigned long delay
, elapsed
, ht
;
2011 if (IS_DEBUG_OSPF_EVENT
)
2012 zlog_debug("SPF: calculation timer scheduled");
2014 /* OSPF instance does not exist. */
2018 ospf_spf_set_reason(reason
);
2020 /* SPF calculation timer is already scheduled. */
2021 if (ospf
->t_spf_calc
) {
2022 if (IS_DEBUG_OSPF_EVENT
)
2024 "SPF: calculation timer is already scheduled: %p",
2025 (void *)ospf
->t_spf_calc
);
2029 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
2031 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
2033 if (ht
> ospf
->spf_max_holdtime
)
2034 ht
= ospf
->spf_max_holdtime
;
2036 /* Get SPF calculation delay time. */
2039 * Got an event within the hold time of last SPF. We need to
2040 * increase the hold_multiplier, if it's not already at/past
2041 * maximum value, and wasn't already increased.
2043 if (ht
< ospf
->spf_max_holdtime
)
2044 ospf
->spf_hold_multiplier
++;
2046 /* always honour the SPF initial delay */
2047 if ((ht
- elapsed
) < ospf
->spf_delay
)
2048 delay
= ospf
->spf_delay
;
2050 delay
= ht
- elapsed
;
2052 /* Event is past required hold-time of last SPF */
2053 delay
= ospf
->spf_delay
;
2054 ospf
->spf_hold_multiplier
= 1;
2057 if (IS_DEBUG_OSPF_EVENT
)
2058 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
2060 ospf
->t_spf_calc
= NULL
;
2061 thread_add_timer_msec(master
, ospf_spf_calculate_schedule_worker
, ospf
,
2062 delay
, &ospf
->t_spf_calc
);
2065 /* Restart OSPF SPF algorithm*/
2066 void ospf_restart_spf(struct ospf
*ospf
)
2068 if (IS_DEBUG_OSPF_EVENT
)
2069 zlog_debug("%s: Restart SPF.", __func__
);
2071 /* Handling inter area and intra area routes*/
2072 if (ospf
->new_table
) {
2073 ospf_route_delete(ospf
, ospf
->new_table
);
2074 ospf_route_table_free(ospf
->new_table
);
2075 ospf
->new_table
= route_table_init();
2078 /* Handling of TYPE-5 lsa(external routes) */
2079 if (ospf
->old_external_route
) {
2080 ospf_route_delete(ospf
, ospf
->old_external_route
);
2081 ospf_route_table_free(ospf
->old_external_route
);
2082 ospf
->old_external_route
= route_table_init();
2086 ospf_spf_calculate_schedule(ospf
, SPF_FLAG_CONFIG_CHANGE
);