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 /* Variables to ensure a SPF scheduled log message is printed only once */
54 static unsigned int spf_reason_flags
= 0;
56 /* dummy vertex to flag "in spftree" */
57 static const struct vertex vertex_in_spftree
= {};
58 #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
59 #define LSA_SPF_NOT_EXPLORED NULL
61 static void ospf_clear_spf_reason_flags(void)
66 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
68 spf_reason_flags
|= 1 << reason
;
71 static void ospf_vertex_free(void *);
74 * Heap related functions, for the managment of the candidates, to
75 * be used with pqueue.
77 static int vertex_cmp(const struct vertex
*v1
, const struct vertex
*v2
)
79 if (v1
->distance
!= v2
->distance
)
80 return v1
->distance
- v2
->distance
;
82 if (v1
->type
!= v2
->type
) {
84 case OSPF_VERTEX_NETWORK
:
86 case OSPF_VERTEX_ROUTER
:
92 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue
, struct vertex
, pqi
, vertex_cmp
);
94 static void lsdb_clean_stat(struct ospf_lsdb
*lsdb
)
96 struct route_table
*table
;
97 struct route_node
*rn
;
101 for (i
= OSPF_MIN_LSA
; i
< OSPF_MAX_LSA
; i
++) {
102 table
= lsdb
->type
[i
].db
;
103 for (rn
= route_top(table
); rn
; rn
= route_next(rn
))
104 if ((lsa
= (rn
->info
)) != NULL
)
105 lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
109 static struct vertex_nexthop
*vertex_nexthop_new(void)
111 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
114 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
116 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
120 * Free the canonical nexthop objects for an area, ie the nexthop objects
121 * attached to the first-hop router vertices, and any intervening network
124 static void ospf_canonical_nexthops_free(struct vertex
*root
)
126 struct listnode
*node
, *nnode
;
127 struct vertex
*child
;
129 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
130 struct listnode
*n2
, *nn2
;
131 struct vertex_parent
*vp
;
134 * router vertices through an attached network each
135 * have a distinct (canonical / not inherited) nexthop
136 * which must be freed.
138 * A network vertex can only have router vertices as its
139 * children, so only one level of recursion is possible.
141 if (child
->type
== OSPF_VERTEX_NETWORK
)
142 ospf_canonical_nexthops_free(child
);
144 /* Free child nexthops pointing back to this root vertex */
145 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
)) {
146 if (vp
->parent
== root
&& vp
->nexthop
) {
147 vertex_nexthop_free(vp
->nexthop
);
149 if (vp
->local_nexthop
) {
150 vertex_nexthop_free(vp
->local_nexthop
);
151 vp
->local_nexthop
= NULL
;
159 * TODO: Parent list should be excised, in favour of maintaining only
160 * vertex_nexthop, with refcounts.
162 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
163 struct vertex_nexthop
*hop
,
164 struct vertex_nexthop
*lhop
)
166 struct vertex_parent
*new;
168 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
171 new->backlink
= backlink
;
173 new->local_nexthop
= lhop
;
178 static void vertex_parent_free(void *p
)
180 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
183 int vertex_parent_cmp(void *aa
, void *bb
)
185 struct vertex_parent
*a
= aa
, *b
= bb
;
186 return IPV4_ADDR_CMP(&a
->nexthop
->router
, &b
->nexthop
->router
);
189 static struct vertex
*ospf_vertex_new(struct ospf_area
*area
,
190 struct ospf_lsa
*lsa
)
194 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
197 new->type
= lsa
->data
->type
;
198 new->id
= lsa
->data
->id
;
199 new->lsa
= lsa
->data
;
200 new->children
= list_new();
201 new->parents
= list_new();
202 new->parents
->del
= vertex_parent_free
;
203 new->parents
->cmp
= vertex_parent_cmp
;
208 listnode_add(area
->spf_vertex_list
, new);
210 if (IS_DEBUG_OSPF_EVENT
)
211 zlog_debug("%s: Created %s vertex %pI4", __func__
,
212 new->type
== OSPF_VERTEX_ROUTER
? "Router"
219 static void ospf_vertex_free(void *data
)
221 struct vertex
*v
= data
;
223 if (IS_DEBUG_OSPF_EVENT
)
224 zlog_debug("%s: Free %s vertex %pI4", __func__
,
225 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
229 list_delete(&v
->children
);
232 list_delete(&v
->parents
);
236 XFREE(MTYPE_OSPF_VERTEX
, v
);
239 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
240 int print_parents
, int print_children
)
242 if (!IS_DEBUG_OSPF_EVENT
)
245 zlog_debug("%s %s vertex %pI4 distance %u flags %u", msg
,
246 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
247 &v
->lsa
->id
, v
->distance
, (unsigned int)v
->flags
);
250 struct listnode
*node
;
251 struct vertex_parent
*vp
;
253 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
256 "parent %pI4 backlink %d nexthop %pI4 lsa pos %d",
257 &vp
->parent
->lsa
->id
, vp
->backlink
,
258 &vp
->nexthop
->router
,
259 vp
->nexthop
->lsa_pos
);
264 if (print_children
) {
265 struct listnode
*cnode
;
268 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
269 ospf_vertex_dump(" child:", cv
, 0, 0);
274 /* Add a vertex to the list of children in each of its parents. */
275 static void ospf_vertex_add_parent(struct vertex
*v
)
277 struct vertex_parent
*vp
;
278 struct listnode
*node
;
280 assert(v
&& v
->parents
);
282 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
283 assert(vp
->parent
&& vp
->parent
->children
);
285 /* No need to add two links from the same parent. */
286 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
287 listnode_add(vp
->parent
->children
, v
);
291 /* Find a vertex according to its router id */
292 struct vertex
*ospf_spf_vertex_find(struct in_addr id
, struct list
*vertex_list
)
294 struct listnode
*node
;
295 struct vertex
*found
;
297 for (ALL_LIST_ELEMENTS_RO(vertex_list
, node
, found
)) {
298 if (found
->id
.s_addr
== id
.s_addr
)
305 /* Find a vertex parent according to its router id */
306 struct vertex_parent
*ospf_spf_vertex_parent_find(struct in_addr id
,
307 struct vertex
*vertex
)
309 struct listnode
*node
;
310 struct vertex_parent
*found
;
312 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, found
)) {
313 if (found
->parent
->id
.s_addr
== id
.s_addr
)
320 struct vertex
*ospf_spf_vertex_by_nexthop(struct vertex
*root
,
321 struct in_addr
*nexthop
)
323 struct listnode
*node
;
324 struct vertex
*child
;
325 struct vertex_parent
*vertex_parent
;
327 for (ALL_LIST_ELEMENTS_RO(root
->children
, node
, child
)) {
328 vertex_parent
= ospf_spf_vertex_parent_find(root
->id
, child
);
329 if (vertex_parent
->nexthop
->router
.s_addr
== nexthop
->s_addr
)
336 /* Create a deep copy of a SPF vertex without children and parents */
337 static struct vertex
*ospf_spf_vertex_copy(struct vertex
*vertex
)
341 copy
= XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
343 memcpy(copy
, vertex
, sizeof(struct vertex
));
344 copy
->parents
= list_new();
345 copy
->parents
->del
= vertex_parent_free
;
346 copy
->parents
->cmp
= vertex_parent_cmp
;
347 copy
->children
= list_new();
352 /* Create a deep copy of a SPF vertex_parent */
353 static struct vertex_parent
*
354 ospf_spf_vertex_parent_copy(struct vertex_parent
*vertex_parent
)
356 struct vertex_parent
*vertex_parent_copy
;
357 struct vertex_nexthop
*nexthop_copy
, *local_nexthop_copy
;
360 XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex_parent
));
362 nexthop_copy
= vertex_nexthop_new();
363 local_nexthop_copy
= vertex_nexthop_new();
365 memcpy(vertex_parent_copy
, vertex_parent
, sizeof(struct vertex_parent
));
366 memcpy(nexthop_copy
, vertex_parent
->nexthop
,
367 sizeof(struct vertex_nexthop
));
368 memcpy(local_nexthop_copy
, vertex_parent
->local_nexthop
,
369 sizeof(struct vertex_nexthop
));
371 vertex_parent_copy
->nexthop
= nexthop_copy
;
372 vertex_parent_copy
->local_nexthop
= local_nexthop_copy
;
374 return vertex_parent_copy
;
377 /* Create a deep copy of a SPF tree */
378 void ospf_spf_copy(struct vertex
*vertex
, struct list
*vertex_list
)
380 struct listnode
*node
;
381 struct vertex
*vertex_copy
, *child
, *child_copy
, *parent_copy
;
382 struct vertex_parent
*vertex_parent
, *vertex_parent_copy
;
384 /* First check if the node is already in the vertex list */
385 vertex_copy
= ospf_spf_vertex_find(vertex
->id
, vertex_list
);
387 vertex_copy
= ospf_spf_vertex_copy(vertex
);
388 listnode_add(vertex_list
, vertex_copy
);
391 /* Copy all parents, create parent nodes if necessary */
392 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, vertex_parent
)) {
393 parent_copy
= ospf_spf_vertex_find(vertex_parent
->parent
->id
,
397 ospf_spf_vertex_copy(vertex_parent
->parent
);
398 listnode_add(vertex_list
, parent_copy
);
400 vertex_parent_copy
= ospf_spf_vertex_parent_copy(vertex_parent
);
401 vertex_parent_copy
->parent
= parent_copy
;
402 listnode_add(vertex_copy
->parents
, vertex_parent_copy
);
405 /* Copy all children, create child nodes if necessary */
406 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
407 child_copy
= ospf_spf_vertex_find(child
->id
, vertex_list
);
409 child_copy
= ospf_spf_vertex_copy(child
);
410 listnode_add(vertex_list
, child_copy
);
412 listnode_add(vertex_copy
->children
, child_copy
);
415 /* Finally continue copying with child nodes */
416 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
))
417 ospf_spf_copy(child
, vertex_list
);
420 static void ospf_spf_remove_branch(struct vertex_parent
*vertex_parent
,
421 struct vertex
*child
,
422 struct list
*vertex_list
)
424 struct listnode
*node
, *nnode
, *inner_node
, *inner_nnode
;
425 struct vertex
*grandchild
;
426 struct vertex_parent
*vertex_parent_found
;
427 bool has_more_links
= false;
430 * First check if there are more nexthops for that parent to that child
432 for (ALL_LIST_ELEMENTS_RO(child
->parents
, node
, vertex_parent_found
)) {
433 if (vertex_parent_found
->parent
->id
.s_addr
434 == vertex_parent
->parent
->id
.s_addr
435 && vertex_parent_found
->nexthop
->router
.s_addr
436 != vertex_parent
->nexthop
->router
.s_addr
)
437 has_more_links
= true;
441 * No more links from that parent? Then delete the child from its
445 listnode_delete(vertex_parent
->parent
->children
, child
);
448 * Delete the vertex_parent from the child parents list, this needs to
451 listnode_delete(child
->parents
, vertex_parent
);
454 * Are there actually more parents left? If not, then delete the child!
455 * This is done by recursively removing the links to the grandchildren,
456 * such that finally the child can be removed without leaving unused
459 if (child
->parents
->count
== 0) {
460 for (ALL_LIST_ELEMENTS(child
->children
, node
, nnode
,
462 for (ALL_LIST_ELEMENTS(grandchild
->parents
, inner_node
,
464 vertex_parent_found
)) {
465 ospf_spf_remove_branch(vertex_parent_found
,
466 grandchild
, vertex_list
);
469 listnode_delete(vertex_list
, child
);
470 ospf_vertex_free(child
);
474 static int ospf_spf_remove_link(struct vertex
*vertex
, struct list
*vertex_list
,
475 struct router_lsa_link
*link
)
477 struct listnode
*node
, *inner_node
;
478 struct vertex
*child
;
479 struct vertex_parent
*vertex_parent
;
482 * Identify the node who shares a subnet (given by the link) with a
483 * child and remove the branch of this particular child.
485 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
486 for (ALL_LIST_ELEMENTS_RO(child
->parents
, inner_node
,
488 if ((vertex_parent
->local_nexthop
->router
.s_addr
489 & link
->link_data
.s_addr
)
490 == (link
->link_id
.s_addr
491 & link
->link_data
.s_addr
)) {
492 ospf_spf_remove_branch(vertex_parent
, child
,
499 /* No link found yet, move on recursively */
500 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
501 if (ospf_spf_remove_link(child
, vertex_list
, link
) == 0)
505 /* link was not removed yet */
509 void ospf_spf_remove_resource(struct vertex
*vertex
, struct list
*vertex_list
,
510 struct protected_resource
*resource
)
512 struct listnode
*node
, *nnode
;
513 struct vertex
*found
;
514 struct vertex_parent
*vertex_parent
;
516 switch (resource
->type
) {
517 case OSPF_TI_LFA_LINK_PROTECTION
:
518 ospf_spf_remove_link(vertex
, vertex_list
, resource
->link
);
520 case OSPF_TI_LFA_NODE_PROTECTION
:
521 found
= ospf_spf_vertex_find(resource
->router_id
, vertex_list
);
526 * Remove the node by removing all links from its parents. Note
527 * that the child is automatically removed here with the last
528 * link from a parent, hence no explicit removal of the node.
530 for (ALL_LIST_ELEMENTS(found
->parents
, node
, nnode
,
532 ospf_spf_remove_branch(vertex_parent
, found
,
542 static void ospf_spf_init(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
543 bool is_dry_run
, bool is_root_node
)
545 struct list
*vertex_list
;
548 /* Create vertex list */
549 vertex_list
= list_new();
550 vertex_list
->del
= ospf_vertex_free
;
551 area
->spf_vertex_list
= vertex_list
;
553 /* Create root node. */
554 v
= ospf_vertex_new(area
, root_lsa
);
557 area
->spf_dry_run
= is_dry_run
;
558 area
->spf_root_node
= is_root_node
;
560 /* Reset ABR and ASBR router counts. */
562 area
->asbr_count
= 0;
565 /* return index of link back to V from W, or -1 if no link found */
566 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
568 unsigned int i
, length
;
569 struct router_lsa
*rl
;
570 struct network_lsa
*nl
;
572 /* In case of W is Network LSA. */
573 if (w
->type
== OSPF_NETWORK_LSA
) {
574 if (v
->type
== OSPF_NETWORK_LSA
)
577 nl
= (struct network_lsa
*)w
;
578 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
580 for (i
= 0; i
< length
; i
++)
581 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
586 /* In case of W is Router LSA. */
587 if (w
->type
== OSPF_ROUTER_LSA
) {
588 rl
= (struct router_lsa
*)w
;
590 length
= ntohs(w
->length
);
592 for (i
= 0; i
< ntohs(rl
->links
)
593 && length
>= sizeof(struct router_lsa
);
595 switch (rl
->link
[i
].type
) {
596 case LSA_LINK_TYPE_POINTOPOINT
:
597 case LSA_LINK_TYPE_VIRTUALLINK
:
599 if (v
->type
== OSPF_ROUTER_LSA
600 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
605 case LSA_LINK_TYPE_TRANSIT
:
606 /* Network LSA ID. */
607 if (v
->type
== OSPF_NETWORK_LSA
608 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
613 case LSA_LINK_TYPE_STUB
:
614 /* Stub can't lead anywhere, carry on */
625 * Find the next link after prev_link from v to w. If prev_link is
626 * NULL, return the first link from v to w. Ignore stub and virtual links;
627 * these link types will never be returned.
629 static struct router_lsa_link
*
630 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
631 struct router_lsa_link
*prev_link
)
635 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
636 struct router_lsa_link
*l
;
638 if (w
->type
== OSPF_VERTEX_ROUTER
)
639 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
641 if (prev_link
== NULL
)
642 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
644 p
= (uint8_t *)prev_link
;
645 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
646 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
649 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
652 l
= (struct router_lsa_link
*)p
;
654 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
655 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
657 if (l
->m
[0].type
!= lsa_type
)
660 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
667 static void ospf_spf_flush_parents(struct vertex
*w
)
669 struct vertex_parent
*vp
;
670 struct listnode
*ln
, *nn
;
672 /* delete the existing nexthops */
673 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
674 list_delete_node(w
->parents
, ln
);
675 vertex_parent_free(vp
);
680 * Consider supplied next-hop for inclusion to the supplied list of
681 * equal-cost next-hops, adjust list as neccessary.
683 static void ospf_spf_add_parent(struct vertex
*v
, struct vertex
*w
,
684 struct vertex_nexthop
*newhop
,
685 struct vertex_nexthop
*newlhop
,
686 unsigned int distance
)
688 struct vertex_parent
*vp
, *wp
;
689 struct listnode
*node
;
691 /* we must have a newhop, and a distance */
692 assert(v
&& w
&& newhop
);
696 * IFF w has already been assigned a distance, then we shouldn't get
697 * here unless callers have determined V(l)->W is shortest /
698 * equal-shortest path (0 is a special case distance (no distance yet
702 assert(distance
<= w
->distance
);
704 w
->distance
= distance
;
706 if (IS_DEBUG_OSPF_EVENT
)
707 zlog_debug("%s: Adding %pI4 as parent of %pI4", __func__
,
708 &v
->lsa
->id
, &w
->lsa
->id
);
711 * Adding parent for a new, better path: flush existing parents from W.
713 if (distance
< w
->distance
) {
714 if (IS_DEBUG_OSPF_EVENT
)
716 "%s: distance %d better than %d, flushing existing parents",
717 __func__
, distance
, w
->distance
);
718 ospf_spf_flush_parents(w
);
719 w
->distance
= distance
;
723 * new parent is <= existing parents, add it to parent list (if nexthop
724 * not on parent list)
726 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
727 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
728 if (IS_DEBUG_OSPF_EVENT
)
730 "%s: ... nexthop already on parent list, skipping add",
736 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
,
738 listnode_add_sort(w
->parents
, vp
);
743 static int match_stub_prefix(struct lsa_header
*lsa
, struct in_addr v_link_addr
,
744 struct in_addr w_link_addr
)
747 struct router_lsa_link
*l
= NULL
;
748 struct in_addr masked_lsa_addr
;
750 if (lsa
->type
!= OSPF_ROUTER_LSA
)
753 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
754 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
757 l
= (struct router_lsa_link
*)p
;
758 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
759 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
761 if (l
->m
[0].type
!= LSA_LINK_TYPE_STUB
)
764 masked_lsa_addr
.s_addr
=
765 (l
->link_id
.s_addr
& l
->link_data
.s_addr
);
767 /* check that both links belong to the same stub subnet */
768 if ((masked_lsa_addr
.s_addr
769 == (v_link_addr
.s_addr
& l
->link_data
.s_addr
))
770 && (masked_lsa_addr
.s_addr
771 == (w_link_addr
.s_addr
& l
->link_data
.s_addr
)))
779 * 16.1.1. Calculate nexthop from root through V (parent) to
780 * vertex W (destination), with given distance from root->W.
782 * The link must be supplied if V is the root vertex. In all other cases
785 * Note that this function may fail, hence the state of the destination
786 * vertex, W, should /not/ be modified in a dependent manner until
787 * this function returns. This function will update the W vertex with the
788 * provided distance as appropriate.
790 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
791 struct vertex
*v
, struct vertex
*w
,
792 struct router_lsa_link
*l
,
793 unsigned int distance
, int lsa_pos
)
795 struct listnode
*node
, *nnode
;
796 struct vertex_nexthop
*nh
, *lnh
;
797 struct vertex_parent
*vp
;
798 unsigned int added
= 0;
800 if (IS_DEBUG_OSPF_EVENT
) {
801 zlog_debug("ospf_nexthop_calculation(): Start");
802 ospf_vertex_dump("V (parent):", v
, 1, 1);
803 ospf_vertex_dump("W (dest) :", w
, 1, 1);
804 zlog_debug("V->W distance: %d", distance
);
807 if (v
== area
->spf
) {
809 * 16.1.1 para 4. In the first case, the parent vertex (V) is
810 * the root (the calculating router itself). This means that
811 * the destination is either a directly connected network or
812 * directly connected router. The outgoing interface in this
813 * case is simply the OSPF interface connecting to the
814 * destination network/router.
817 /* we *must* be supplied with the link data */
820 if (IS_DEBUG_OSPF_EVENT
)
822 "%s: considering link type:%d link_id:%pI4 link_data:%pI4",
823 __func__
, l
->m
[0].type
, &l
->link_id
,
826 if (w
->type
== OSPF_VERTEX_ROUTER
) {
828 * l is a link from v to w l2 will be link from w to v
830 struct router_lsa_link
*l2
= NULL
;
832 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
833 struct ospf_interface
*oi
= NULL
;
834 struct in_addr nexthop
= {.s_addr
= 0};
836 if (area
->spf_root_node
) {
837 oi
= ospf_if_lookup_by_lsa_pos(area
,
841 "%s: OI not found in LSA: lsa_pos: %d link_id:%pI4 link_data:%pI4",
850 * If the destination is a router which connects
851 * to the calculating router via a
852 * Point-to-MultiPoint network, the
853 * destination's next hop IP address(es) can be
854 * determined by examining the destination's
855 * router-LSA: each link pointing back to the
856 * calculating router and having a Link Data
857 * field belonging to the Point-to-MultiPoint
858 * network provides an IP address of the next
861 * At this point l is a link from V to W, and V
862 * is the root ("us"). If it is a point-to-
863 * multipoint interface, then look through the
864 * links in the opposite direction (W to V).
865 * If any of them have an address that lands
866 * within the subnet declared by the PtMP link,
867 * then that link is a constituent of the PtMP
868 * link, and its address is a nexthop address
871 * Note for point-to-point interfaces:
873 * Having nexthop = 0 (as proposed in the RFC)
874 * is tempting, but NOT acceptable. It breaks
875 * AS-External routes with a forwarding address,
876 * since ospf_ase_complete_direct_routes() will
877 * mistakenly assume we've reached the last hop
878 * and should place the forwarding address as
879 * nexthop. Also, users may configure multi-
880 * access links in p2p mode, so we need the IP
881 * to ARP the nexthop.
883 * If the calculating router is the SPF root
884 * node and the link is P2P then access the
885 * interface information directly. This can be
886 * crucial when e.g. IP unnumbered is used
887 * where 'correct' nexthop information are not
888 * available via Router LSAs.
890 * Otherwise handle P2P and P2MP the same way
891 * as described above using a reverse lookup to
892 * figure out the nexthop.
896 * HACK: we don't know (yet) how to distinguish
897 * between P2P and P2MP interfaces by just
898 * looking at LSAs, which is important for
899 * TI-LFA since you want to do SPF calculations
900 * from the perspective of other nodes. Since
901 * TI-LFA is currently not implemented for P2MP
902 * we just check here if it is enabled and then
903 * blindly assume that P2P is used. Ultimately
904 * the interface code needs to be removed
907 if (area
->ospf
->ti_lfa_enabled
908 || (oi
&& oi
->type
== OSPF_IFTYPE_POINTOPOINT
)) {
909 struct ospf_neighbor
*nbr_w
= NULL
;
911 /* Calculating node is root node, link
913 if (area
->spf_root_node
) {
914 nbr_w
= ospf_nbr_lookup_by_routerid(
915 oi
->nbrs
, &l
->link_id
);
918 nexthop
= nbr_w
->src
;
924 while ((l2
= ospf_get_next_link(
926 if (match_stub_prefix(
937 } else if (oi
&& oi
->type
938 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
939 struct prefix_ipv4 la
;
942 la
.prefixlen
= oi
->address
->prefixlen
;
945 * V links to W on PtMP interface;
946 * find the interface address on W
948 while ((l2
= ospf_get_next_link(w
, v
,
950 la
.prefix
= l2
->link_data
;
952 if (prefix_cmp((struct prefix
958 nexthop
= l2
->link_data
;
964 nh
= vertex_nexthop_new();
965 nh
->router
= nexthop
;
966 nh
->lsa_pos
= lsa_pos
;
969 * Since v is the root the nexthop and
970 * local nexthop are the same.
972 lnh
= vertex_nexthop_new();
974 sizeof(struct vertex_nexthop
));
976 ospf_spf_add_parent(v
, w
, nh
, lnh
,
981 "%s: could not determine nexthop for link %s",
982 __func__
, oi
? oi
->ifp
->name
: "");
983 } /* end point-to-point link from V to W */
984 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
986 * VLink implementation limitations:
987 * a) vl_data can only reference one nexthop,
988 * so no ECMP to backbone through VLinks.
989 * Though transit-area summaries may be
990 * considered, and those can be ECMP.
991 * b) We can only use /one/ VLink, even if
992 * multiple ones exist this router through
993 * multiple transit-areas.
996 struct ospf_vl_data
*vl_data
;
998 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
1002 && CHECK_FLAG(vl_data
->flags
,
1003 OSPF_VL_FLAG_APPROVED
)) {
1004 nh
= vertex_nexthop_new();
1005 nh
->router
= vl_data
->nexthop
.router
;
1006 nh
->lsa_pos
= vl_data
->nexthop
.lsa_pos
;
1009 * Since v is the root the nexthop and
1010 * local nexthop are the same.
1012 lnh
= vertex_nexthop_new();
1014 sizeof(struct vertex_nexthop
));
1016 ospf_spf_add_parent(v
, w
, nh
, lnh
,
1021 "ospf_nexthop_calculation(): vl_data for VL link not found");
1022 } /* end virtual-link from V to W */
1024 } /* end W is a Router vertex */
1026 assert(w
->type
== OSPF_VERTEX_NETWORK
);
1028 nh
= vertex_nexthop_new();
1029 nh
->router
.s_addr
= 0; /* Nexthop not required */
1030 nh
->lsa_pos
= lsa_pos
;
1033 * Since v is the root the nexthop and
1034 * local nexthop are the same.
1036 lnh
= vertex_nexthop_new();
1037 memcpy(lnh
, nh
, sizeof(struct vertex_nexthop
));
1039 ospf_spf_add_parent(v
, w
, nh
, lnh
, distance
);
1042 } /* end V is the root */
1043 /* Check if W's parent is a network connected to root. */
1044 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
1045 /* See if any of V's parents are the root. */
1046 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1047 if (vp
->parent
== area
->spf
) {
1049 * 16.1.1 para 5. ...the parent vertex is a
1050 * network that directly connects the
1051 * calculating router to the destination
1052 * router. The list of next hops is then
1053 * determined by examining the destination's
1057 assert(w
->type
== OSPF_VERTEX_ROUTER
);
1058 while ((l
= ospf_get_next_link(w
, v
, l
))) {
1060 * ... For each link in the router-LSA
1061 * that points back to the parent
1062 * network, the link's Link Data field
1063 * provides the IP address of a next hop
1064 * router. The outgoing interface to use
1065 * can then be derived from the next
1066 * hop IP address (or it can be
1067 * inherited from the parent network).
1069 nh
= vertex_nexthop_new();
1070 nh
->router
= l
->link_data
;
1071 nh
->lsa_pos
= vp
->nexthop
->lsa_pos
;
1074 * Since v is the root the nexthop and
1075 * local nexthop are the same.
1077 lnh
= vertex_nexthop_new();
1079 sizeof(struct vertex_nexthop
));
1082 ospf_spf_add_parent(v
, w
, nh
, lnh
,
1086 * Note lack of return is deliberate. See next
1092 * NB: This code is non-trivial.
1094 * E.g. it is not enough to know that V connects to the root. It
1095 * is also important that the while above, looping through all
1096 * links from W->V found at least one link, so that we know
1097 * there is bi-directional connectivity between V and W (which
1098 * need not be the case, e.g. when OSPF has not yet converged
1099 * fully). Otherwise, if we /always/ return here, without having
1100 * checked that root->V->-W actually resulted in a valid nexthop
1101 * being created, then we we will prevent SPF from finding/using
1102 * higher cost paths.
1104 * It is important, if root->V->W has not been added, that we
1105 * continue through to the intervening-router nexthop code
1106 * below. So as to ensure other paths to V may be used. This
1107 * avoids unnecessary blackholes while OSPF is converging.
1109 * I.e. we may have arrived at this function, examining V -> W,
1110 * via workable paths other than root -> V, and it's important
1111 * to avoid getting "confused" by non-working root->V->W path
1112 * - it's important to *not* lose the working non-root paths,
1113 * just because of a non-viable root->V->W.
1120 * 16.1.1 para 4. If there is at least one intervening router in the
1121 * current shortest path between the destination and the root, the
1122 * destination simply inherits the set of next hops from the
1125 if (IS_DEBUG_OSPF_EVENT
)
1126 zlog_debug("%s: Intervening routers, adding parent(s)",
1129 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1133 * The nexthop is inherited, but the local nexthop still needs
1137 lnh
= vertex_nexthop_new();
1138 lnh
->router
= l
->link_data
;
1139 lnh
->lsa_pos
= lsa_pos
;
1144 ospf_spf_add_parent(v
, w
, vp
->nexthop
, lnh
, distance
);
1150 static int ospf_spf_is_protected_resource(struct ospf_area
*area
,
1151 struct router_lsa_link
*link
,
1152 struct lsa_header
*lsa
)
1155 struct router_lsa_link
*p_link
;
1156 struct router_lsa_link
*l
= NULL
;
1157 struct in_addr router_id
;
1160 if (!area
->spf_protected_resource
)
1163 link_type
= link
->m
[0].type
;
1165 switch (area
->spf_protected_resource
->type
) {
1166 case OSPF_TI_LFA_LINK_PROTECTION
:
1167 p_link
= area
->spf_protected_resource
->link
;
1171 /* For P2P: check if the link belongs to the same subnet */
1172 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1173 && (p_link
->link_id
.s_addr
& p_link
->link_data
.s_addr
)
1174 == (link
->link_data
.s_addr
1175 & p_link
->link_data
.s_addr
))
1178 /* For stub: check if this the same subnet */
1179 if (link_type
== LSA_LINK_TYPE_STUB
1180 && (p_link
->link_id
.s_addr
== link
->link_id
.s_addr
)
1181 && (p_link
->link_data
.s_addr
== link
->link_data
.s_addr
))
1185 case OSPF_TI_LFA_NODE_PROTECTION
:
1186 router_id
= area
->spf_protected_resource
->router_id
;
1187 if (router_id
.s_addr
== INADDR_ANY
)
1190 /* For P2P: check if the link leads to the protected node */
1191 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1192 && link
->link_id
.s_addr
== router_id
.s_addr
)
1195 /* The rest is about stub links! */
1196 if (link_type
!= LSA_LINK_TYPE_STUB
)
1200 * Check if there's a P2P link in the router LSA with the
1201 * corresponding link data in the same subnet.
1204 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1205 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
1208 l
= (struct router_lsa_link
*)p
;
1209 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1210 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1212 /* We only care about P2P with the proper link id */
1213 if ((l
->m
[0].type
!= LSA_LINK_TYPE_POINTOPOINT
)
1214 || (l
->link_id
.s_addr
!= router_id
.s_addr
))
1217 /* Link data in the subnet given by the link? */
1218 if ((link
->link_id
.s_addr
& link
->link_data
.s_addr
)
1219 == (l
->link_data
.s_addr
& link
->link_data
.s_addr
))
1224 case OSPF_TI_LFA_UNDEFINED_PROTECTION
:
1232 * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
1233 * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
1234 * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
1235 * corresponding link in the LSA of W and extract the particular weight.
1237 * TODO: Only P2P supported by now!
1239 static uint16_t get_reverse_distance(struct vertex
*v
,
1240 struct router_lsa_link
*l
,
1241 struct ospf_lsa
*w_lsa
)
1244 struct router_lsa_link
*w_link
;
1245 uint16_t distance
= 0;
1247 assert(w_lsa
&& w_lsa
->data
);
1249 p
= ((uint8_t *)w_lsa
->data
) + OSPF_LSA_HEADER_SIZE
+ 4;
1250 lim
= ((uint8_t *)w_lsa
->data
) + ntohs(w_lsa
->data
->length
);
1253 w_link
= (struct router_lsa_link
*)p
;
1254 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1255 + (w_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1257 /* Only care about P2P with link ID equal to V's router id */
1258 if (w_link
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
1259 && w_link
->link_id
.s_addr
== v
->id
.s_addr
) {
1260 distance
= ntohs(w_link
->m
[0].metric
);
1266 * This might happen if the LSA for W is not complete yet. In this
1267 * case we take the weight of the 'forward' link from V. When the LSA
1268 * for W is completed the reverse SPF is run again anyway.
1271 distance
= ntohs(l
->m
[0].metric
);
1273 if (IS_DEBUG_OSPF_EVENT
)
1274 zlog_debug("%s: reversed distance is %u", __func__
, distance
);
1281 * v is on the SPF tree. Examine the links in v's LSA. Update the list of
1282 * candidates with any vertices not already on the list. If a lower-cost path
1283 * is found to a vertex already on the candidate list, store the new cost.
1285 static void ospf_spf_next(struct vertex
*v
, struct ospf_area
*area
,
1286 struct vertex_pqueue_head
*candidate
)
1288 struct ospf_lsa
*w_lsa
= NULL
;
1291 struct router_lsa_link
*l
= NULL
;
1293 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
1294 uint16_t link_distance
;
1297 * If this is a router-LSA, and bit V of the router-LSA (see Section
1298 * A.4.2:RFC2328) is set, set Area A's TransitCapability to true.
1300 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1301 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
1302 area
->transit
= OSPF_TRANSIT_TRUE
;
1305 if (IS_DEBUG_OSPF_EVENT
)
1306 zlog_debug("%s: Next vertex of %s vertex %pI4", __func__
,
1307 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
1310 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1311 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1315 unsigned int distance
;
1317 /* In case of V is Router-LSA. */
1318 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
1319 l
= (struct router_lsa_link
*)p
;
1321 lsa_pos
= lsa_pos_next
; /* LSA link position */
1324 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1325 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1328 * (a) If this is a link to a stub network, examine the
1329 * next link in V's LSA. Links to stub networks will
1330 * be considered in the second stage of the shortest
1333 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
1337 * Don't process TI-LFA protected resources.
1339 * TODO: Replace this by a proper solution, e.g. remove
1340 * corresponding links from the LSDB and run the SPF
1341 * algo with the stripped-down LSDB.
1343 if (ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1347 * (b) Otherwise, W is a transit vertex (router or
1348 * transit network). Look up the vertex W's LSA
1349 * (router-LSA or network-LSA) in Area A's link state
1353 case LSA_LINK_TYPE_POINTOPOINT
:
1354 case LSA_LINK_TYPE_VIRTUALLINK
:
1355 if (type
== LSA_LINK_TYPE_VIRTUALLINK
1356 && IS_DEBUG_OSPF_EVENT
)
1358 "looking up LSA through VL: %pI4",
1360 w_lsa
= ospf_lsa_lookup(area
->ospf
, area
,
1362 l
->link_id
, l
->link_id
);
1363 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1364 zlog_debug("found Router LSA %pI4",
1367 case LSA_LINK_TYPE_TRANSIT
:
1368 if (IS_DEBUG_OSPF_EVENT
)
1370 "Looking up Network LSA, ID: %pI4",
1372 w_lsa
= ospf_lsa_lookup_by_id(
1373 area
, OSPF_NETWORK_LSA
, l
->link_id
);
1374 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1375 zlog_debug("found the LSA");
1378 flog_warn(EC_OSPF_LSA
,
1379 "Invalid LSA link type %d", type
);
1384 * For TI-LFA we might need the reverse SPF.
1385 * Currently only works with P2P!
1387 if (type
== LSA_LINK_TYPE_POINTOPOINT
1388 && area
->spf_reversed
)
1390 get_reverse_distance(v
, l
, w_lsa
);
1392 link_distance
= ntohs(l
->m
[0].metric
);
1394 /* step (d) below */
1395 distance
= v
->distance
+ link_distance
;
1397 /* In case of V is Network-LSA. */
1398 r
= (struct in_addr
*)p
;
1399 p
+= sizeof(struct in_addr
);
1401 /* Lookup the vertex W's LSA. */
1402 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
1404 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1405 zlog_debug("found Router LSA %pI4",
1408 /* step (d) below */
1409 distance
= v
->distance
;
1413 * (b cont.) If the LSA does not exist, or its LS age is equal
1414 * to MaxAge, or it does not have a link back to vertex V,
1415 * examine the next link in V's LSA.[23]
1417 if (w_lsa
== NULL
) {
1418 if (IS_DEBUG_OSPF_EVENT
)
1419 zlog_debug("No LSA found");
1423 if (IS_LSA_MAXAGE(w_lsa
)) {
1424 if (IS_DEBUG_OSPF_EVENT
)
1425 zlog_debug("LSA is MaxAge");
1429 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
1430 if (IS_DEBUG_OSPF_EVENT
)
1431 zlog_debug("The LSA doesn't have a link back");
1436 * (c) If vertex W is already on the shortest-path tree, examine
1437 * the next link in the LSA.
1439 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
1440 if (IS_DEBUG_OSPF_EVENT
)
1441 zlog_debug("The LSA is already in SPF");
1446 * (d) Calculate the link state cost D of the resulting path
1447 * from the root to vertex W. D is equal to the sum of the link
1448 * state cost of the (already calculated) shortest path to
1449 * vertex V and the advertised cost of the link between vertices
1453 /* calculate link cost D -- moved above */
1455 /* Is there already vertex W in candidate list? */
1456 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
1457 /* prepare vertex W. */
1458 w
= ospf_vertex_new(area
, w_lsa
);
1460 /* Calculate nexthop to W. */
1461 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
1463 vertex_pqueue_add(candidate
, w
);
1464 else if (IS_DEBUG_OSPF_EVENT
)
1465 zlog_debug("Nexthop Calc failed");
1466 } else if (w_lsa
->stat
!= LSA_SPF_IN_SPFTREE
) {
1468 if (w
->distance
< distance
) {
1471 else if (w
->distance
== distance
) {
1473 * Found an equal-cost path to W.
1474 * Calculate nexthop of to W from V.
1476 ospf_nexthop_calculation(area
, v
, w
, l
,
1481 * Found a lower-cost path to W.
1482 * nexthop_calculation is conditional, if it
1483 * finds valid nexthop it will call
1484 * spf_add_parents, which will flush the old
1487 vertex_pqueue_del(candidate
, w
);
1488 ospf_nexthop_calculation(area
, v
, w
, l
,
1490 vertex_pqueue_add(candidate
, w
);
1492 } /* end W is already on the candidate list */
1493 } /* end loop over the links in V's LSA */
1496 static void ospf_spf_dump(struct vertex
*v
, int i
)
1498 struct listnode
*cnode
;
1499 struct listnode
*nnode
;
1500 struct vertex_parent
*parent
;
1502 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1503 if (IS_DEBUG_OSPF_EVENT
)
1504 zlog_debug("SPF Result: %d [R] %pI4", i
,
1507 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1508 if (IS_DEBUG_OSPF_EVENT
)
1509 zlog_debug("SPF Result: %d [N] %pI4/%d", i
,
1511 ip_masklen(lsa
->mask
));
1514 if (IS_DEBUG_OSPF_EVENT
)
1515 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1516 zlog_debug(" nexthop %p %pI4 %d",
1517 (void *)parent
->nexthop
,
1518 &parent
->nexthop
->router
,
1519 parent
->nexthop
->lsa_pos
);
1524 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1525 ospf_spf_dump(v
, i
);
1528 void ospf_spf_print(struct vty
*vty
, struct vertex
*v
, int i
)
1530 struct listnode
*cnode
;
1531 struct listnode
*nnode
;
1532 struct vertex_parent
*parent
;
1534 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1535 vty_out(vty
, "SPF Result: depth %d [R] %pI4\n", i
, &v
->lsa
->id
);
1537 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1538 vty_out(vty
, "SPF Result: depth %d [N] %pI4/%d\n", i
,
1539 &v
->lsa
->id
, ip_masklen(lsa
->mask
));
1542 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1544 " nexthop %pI4 lsa pos %d -- local nexthop %pI4 lsa pos %d\n",
1545 &parent
->nexthop
->router
, parent
->nexthop
->lsa_pos
,
1546 &parent
->local_nexthop
->router
,
1547 parent
->local_nexthop
->lsa_pos
);
1552 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1553 ospf_spf_print(vty
, v
, i
);
1556 /* Second stage of SPF calculation. */
1557 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1558 struct route_table
*rt
, int parent_is_root
)
1560 struct listnode
*cnode
, *cnnode
;
1561 struct vertex
*child
;
1563 if (IS_DEBUG_OSPF_EVENT
)
1564 zlog_debug("ospf_process_stub():processing stubs for area %pI4",
1567 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1570 struct router_lsa_link
*l
;
1571 struct router_lsa
*router_lsa
;
1574 if (IS_DEBUG_OSPF_EVENT
)
1576 "ospf_process_stubs():processing router LSA, id: %pI4",
1579 router_lsa
= (struct router_lsa
*)v
->lsa
;
1581 if (IS_DEBUG_OSPF_EVENT
)
1583 "ospf_process_stubs(): we have %d links to process",
1584 ntohs(router_lsa
->links
));
1586 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1587 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1590 l
= (struct router_lsa_link
*)p
;
1592 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1593 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1595 /* Don't process TI-LFA protected resources */
1596 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
1597 && !ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1598 ospf_intra_add_stub(rt
, l
, v
, area
,
1599 parent_is_root
, lsa_pos
);
1604 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1607 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1608 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1612 * The first level of routers connected to the root
1613 * should have 'parent_is_root' set, including those
1614 * connected via a network vertex.
1618 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1621 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1623 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1627 void ospf_rtrs_free(struct route_table
*rtrs
)
1629 struct route_node
*rn
;
1630 struct list
*or_list
;
1631 struct ospf_route
* or ;
1632 struct listnode
*node
, *nnode
;
1634 if (IS_DEBUG_OSPF_EVENT
)
1635 zlog_debug("Route: Router Routing Table free");
1637 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1638 if ((or_list
= rn
->info
) != NULL
) {
1639 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1640 ospf_route_free(or);
1642 list_delete(&or_list
);
1644 /* Unlock the node. */
1646 route_unlock_node(rn
);
1649 route_table_finish(rtrs
);
1652 void ospf_spf_cleanup(struct vertex
*spf
, struct list
*vertex_list
)
1655 * Free nexthop information, canonical versions of which are
1656 * attached the first level of router vertices attached to the
1657 * root vertex, see ospf_nexthop_calculation.
1660 ospf_canonical_nexthops_free(spf
);
1662 /* Free SPF vertices list with deconstructor ospf_vertex_free. */
1664 list_delete(&vertex_list
);
1667 /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */
1668 void ospf_spf_calculate(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
1669 struct route_table
*new_table
,
1670 struct route_table
*new_rtrs
, bool is_dry_run
,
1673 struct vertex_pqueue_head candidate
;
1676 if (IS_DEBUG_OSPF_EVENT
) {
1677 zlog_debug("ospf_spf_calculate: Start");
1678 zlog_debug("ospf_spf_calculate: running Dijkstra for area %pI4",
1683 * If the router LSA of the root is not yet allocated, return this
1684 * area's calculation. In the 'usual' case the root_lsa is the
1685 * self-originated router LSA of the node itself.
1688 if (IS_DEBUG_OSPF_EVENT
)
1690 "ospf_spf_calculate: Skip area %pI4's calculation due to empty root LSA",
1695 /* Initialize the algorithm's data structures, see RFC2328 16.1. (1). */
1698 * This function scans all the LSA database and set the stat field to
1699 * LSA_SPF_NOT_EXPLORED.
1701 lsdb_clean_stat(area
->lsdb
);
1703 /* Create a new heap for the candidates. */
1704 vertex_pqueue_init(&candidate
);
1707 * Initialize the shortest-path tree to only the root (which is usually
1708 * the router doing the calculation).
1710 ospf_spf_init(area
, root_lsa
, is_dry_run
, is_root_node
);
1712 /* Set Area A's TransitCapability to false. */
1713 area
->transit
= OSPF_TRANSIT_FALSE
;
1714 area
->shortcut_capability
= 1;
1717 * Use the root vertex for the start of the SPF algorithm and make it
1721 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1724 /* RFC2328 16.1. (2). */
1725 ospf_spf_next(v
, area
, &candidate
);
1727 /* RFC2328 16.1. (3). */
1728 v
= vertex_pqueue_pop(&candidate
);
1730 /* No more vertices left. */
1733 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1735 ospf_vertex_add_parent(v
);
1737 /* RFC2328 16.1. (4). */
1738 if (v
->type
== OSPF_VERTEX_ROUTER
)
1739 ospf_intra_add_router(new_rtrs
, v
, area
);
1741 ospf_intra_add_transit(new_table
, v
, area
);
1743 /* Iterate back to (2), see RFC2328 16.1. (5). */
1746 if (IS_DEBUG_OSPF_EVENT
) {
1747 ospf_spf_dump(area
->spf
, 0);
1748 ospf_route_table_dump(new_table
);
1752 * Second stage of SPF calculation procedure's, add leaves to the tree
1753 * for stub networks.
1755 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1757 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1759 /* Increment SPF Calculation Counter. */
1760 area
->spf_calculation
++;
1762 monotime(&area
->ospf
->ts_spf
);
1763 area
->ts_spf
= area
->ospf
->ts_spf
;
1765 if (IS_DEBUG_OSPF_EVENT
)
1766 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1767 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1770 void ospf_spf_calculate_area(struct ospf
*ospf
, struct ospf_area
*area
,
1771 struct route_table
*new_table
,
1772 struct route_table
*new_rtrs
)
1774 ospf_spf_calculate(area
, area
->router_lsa_self
, new_table
, new_rtrs
,
1777 if (ospf
->ti_lfa_enabled
)
1778 ospf_ti_lfa_compute(area
, new_table
,
1779 ospf
->ti_lfa_protection_type
);
1781 ospf_spf_cleanup(area
->spf
, area
->spf_vertex_list
);
1784 void ospf_spf_calculate_areas(struct ospf
*ospf
, struct route_table
*new_table
,
1785 struct route_table
*new_rtrs
)
1787 struct ospf_area
*area
;
1788 struct listnode
*node
, *nnode
;
1790 /* Calculate SPF for each area. */
1791 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1792 /* Do backbone last, so as to first discover intra-area paths
1793 * for any back-bone virtual-links */
1794 if (ospf
->backbone
&& ospf
->backbone
== area
)
1797 ospf_spf_calculate_area(ospf
, area
, new_table
, new_rtrs
);
1800 /* SPF for backbone, if required */
1802 ospf_spf_calculate_area(ospf
, ospf
->backbone
, new_table
,
1806 /* Worker for SPF calculation scheduler. */
1807 static int ospf_spf_calculate_schedule_worker(struct thread
*thread
)
1809 struct ospf
*ospf
= THREAD_ARG(thread
);
1810 struct route_table
*new_table
, *new_rtrs
;
1811 struct timeval start_time
, spf_start_time
;
1812 unsigned long ia_time
, prune_time
, rt_time
;
1813 unsigned long abr_time
, total_spf_time
, spf_time
;
1814 char rbuf
[32]; /* reason_buf */
1816 if (IS_DEBUG_OSPF_EVENT
)
1817 zlog_debug("SPF: Timer (SPF calculation expire)");
1819 ospf
->t_spf_calc
= NULL
;
1821 ospf_vl_unapprove(ospf
);
1823 /* Execute SPF for each area including backbone, see RFC 2328 16.1. */
1824 monotime(&spf_start_time
);
1825 new_table
= route_table_init(); /* routing table */
1826 new_rtrs
= route_table_init(); /* ABR/ASBR routing table */
1827 ospf_spf_calculate_areas(ospf
, new_table
, new_rtrs
);
1828 spf_time
= monotime_since(&spf_start_time
, NULL
);
1830 ospf_vl_shut_unapproved(ospf
);
1832 /* Calculate inter-area routes, see RFC 2328 16.2. */
1833 monotime(&start_time
);
1834 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1835 ia_time
= monotime_since(&start_time
, NULL
);
1837 /* Get rid of transit networks and routers we cannot reach anyway. */
1838 monotime(&start_time
);
1839 ospf_prune_unreachable_networks(new_table
);
1840 ospf_prune_unreachable_routers(new_rtrs
);
1841 prune_time
= monotime_since(&start_time
, NULL
);
1843 /* Note: RFC 2328 16.3. is apparently missing. */
1846 * Calculate AS external routes, see RFC 2328 16.4.
1847 * There is a dedicated routing table for external routes which is not
1848 * handled here directly
1850 ospf_ase_calculate_schedule(ospf
);
1851 ospf_ase_calculate_timer_add(ospf
);
1853 if (IS_DEBUG_OSPF_EVENT
)
1855 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1856 __func__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1857 ospf
->vrf_id
, new_table
->count
);
1859 /* Update routing table. */
1860 monotime(&start_time
);
1861 ospf_route_install(ospf
, new_table
);
1862 rt_time
= monotime_since(&start_time
, NULL
);
1864 /* Free old ABR/ASBR routing table */
1866 /* ospf_route_delete (ospf->old_rtrs); */
1867 ospf_rtrs_free(ospf
->old_rtrs
);
1869 /* Update ABR/ASBR routing table */
1870 ospf
->old_rtrs
= ospf
->new_rtrs
;
1871 ospf
->new_rtrs
= new_rtrs
;
1873 /* ABRs may require additional changes, see RFC 2328 16.7. */
1874 monotime(&start_time
);
1875 if (IS_OSPF_ABR(ospf
)) {
1877 ospf_abr_nssa_check_status(ospf
);
1878 ospf_abr_task(ospf
);
1880 abr_time
= monotime_since(&start_time
, NULL
);
1882 /* Schedule Segment Routing update */
1883 ospf_sr_update_task(ospf
);
1886 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1889 if (spf_reason_flags
) {
1890 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1891 strlcat(rbuf
, "R, ", sizeof(rbuf
));
1892 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1893 strlcat(rbuf
, "N, ", sizeof(rbuf
));
1894 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1895 strlcat(rbuf
, "S, ", sizeof(rbuf
));
1896 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1897 strlcat(rbuf
, "AS, ", sizeof(rbuf
));
1898 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1899 strlcat(rbuf
, "ABR, ", sizeof(rbuf
));
1900 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1901 strlcat(rbuf
, "ASBR, ", sizeof(rbuf
));
1902 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1903 strlcat(rbuf
, "M, ", sizeof(rbuf
));
1905 size_t rbuflen
= strlen(rbuf
);
1907 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1912 if (IS_DEBUG_OSPF_EVENT
) {
1913 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1914 zlog_info(" SPF Time: %ld", spf_time
);
1915 zlog_info(" InterArea: %ld", ia_time
);
1916 zlog_info(" Prune: %ld", prune_time
);
1917 zlog_info(" RouteInstall: %ld", rt_time
);
1918 if (IS_OSPF_ABR(ospf
))
1919 zlog_info(" ABR: %ld (%d areas)",
1920 abr_time
, ospf
->areas
->count
);
1921 zlog_info("Reason(s) for SPF: %s", rbuf
);
1924 ospf_clear_spf_reason_flags();
1930 * Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer
1933 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1935 unsigned long delay
, elapsed
, ht
;
1937 if (IS_DEBUG_OSPF_EVENT
)
1938 zlog_debug("SPF: calculation timer scheduled");
1940 /* OSPF instance does not exist. */
1944 ospf_spf_set_reason(reason
);
1946 /* SPF calculation timer is already scheduled. */
1947 if (ospf
->t_spf_calc
) {
1948 if (IS_DEBUG_OSPF_EVENT
)
1950 "SPF: calculation timer is already scheduled: %p",
1951 (void *)ospf
->t_spf_calc
);
1955 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
1957 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1959 if (ht
> ospf
->spf_max_holdtime
)
1960 ht
= ospf
->spf_max_holdtime
;
1962 /* Get SPF calculation delay time. */
1965 * Got an event within the hold time of last SPF. We need to
1966 * increase the hold_multiplier, if it's not already at/past
1967 * maximum value, and wasn't already increased.
1969 if (ht
< ospf
->spf_max_holdtime
)
1970 ospf
->spf_hold_multiplier
++;
1972 /* always honour the SPF initial delay */
1973 if ((ht
- elapsed
) < ospf
->spf_delay
)
1974 delay
= ospf
->spf_delay
;
1976 delay
= ht
- elapsed
;
1978 /* Event is past required hold-time of last SPF */
1979 delay
= ospf
->spf_delay
;
1980 ospf
->spf_hold_multiplier
= 1;
1983 if (IS_DEBUG_OSPF_EVENT
)
1984 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
1986 ospf
->t_spf_calc
= NULL
;
1987 thread_add_timer_msec(master
, ospf_spf_calculate_schedule_worker
, ospf
,
1988 delay
, &ospf
->t_spf_calc
);