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 #include "ospfd/ospf_orr.h"
58 /* Variables to ensure a SPF scheduled log message is printed only once */
60 static unsigned int spf_reason_flags
= 0;
62 /* dummy vertex to flag "in spftree" */
63 static const struct vertex vertex_in_spftree
= {};
64 #define LSA_SPF_IN_SPFTREE (struct vertex *)&vertex_in_spftree
65 #define LSA_SPF_NOT_EXPLORED NULL
67 static void ospf_clear_spf_reason_flags(void)
72 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
74 spf_reason_flags
|= 1 << reason
;
77 static void ospf_vertex_free(void *);
80 * Heap related functions, for the managment of the candidates, to
81 * be used with pqueue.
83 static int vertex_cmp(const struct vertex
*v1
, const struct vertex
*v2
)
85 if (v1
->distance
!= v2
->distance
)
86 return v1
->distance
- v2
->distance
;
88 if (v1
->type
!= v2
->type
) {
90 case OSPF_VERTEX_NETWORK
:
92 case OSPF_VERTEX_ROUTER
:
98 DECLARE_SKIPLIST_NONUNIQ(vertex_pqueue
, struct vertex
, pqi
, vertex_cmp
);
100 static void lsdb_clean_stat(struct ospf_lsdb
*lsdb
)
102 struct route_table
*table
;
103 struct route_node
*rn
;
104 struct ospf_lsa
*lsa
;
107 for (i
= OSPF_MIN_LSA
; i
< OSPF_MAX_LSA
; i
++) {
108 table
= lsdb
->type
[i
].db
;
109 for (rn
= route_top(table
); rn
; rn
= route_next(rn
))
110 if ((lsa
= (rn
->info
)) != NULL
)
111 lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
115 static struct vertex_nexthop
*vertex_nexthop_new(void)
117 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
120 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
122 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
126 * Free the canonical nexthop objects for an area, ie the nexthop objects
127 * attached to the first-hop router vertices, and any intervening network
130 static void ospf_canonical_nexthops_free(struct vertex
*root
)
132 struct listnode
*node
, *nnode
;
133 struct vertex
*child
;
135 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
136 struct listnode
*n2
, *nn2
;
137 struct vertex_parent
*vp
;
140 * router vertices through an attached network each
141 * have a distinct (canonical / not inherited) nexthop
142 * which must be freed.
144 * A network vertex can only have router vertices as its
145 * children, so only one level of recursion is possible.
147 if (child
->type
== OSPF_VERTEX_NETWORK
)
148 ospf_canonical_nexthops_free(child
);
150 /* Free child nexthops pointing back to this root vertex */
151 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
)) {
152 if (vp
->parent
== root
&& vp
->nexthop
) {
153 vertex_nexthop_free(vp
->nexthop
);
155 if (vp
->local_nexthop
) {
156 vertex_nexthop_free(vp
->local_nexthop
);
157 vp
->local_nexthop
= NULL
;
165 * TODO: Parent list should be excised, in favour of maintaining only
166 * vertex_nexthop, with refcounts.
168 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
169 struct vertex_nexthop
*hop
,
170 struct vertex_nexthop
*lhop
)
172 struct vertex_parent
*new;
174 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
177 new->backlink
= backlink
;
179 new->local_nexthop
= lhop
;
184 static void vertex_parent_free(struct vertex_parent
*p
)
186 vertex_nexthop_free(p
->local_nexthop
);
187 vertex_nexthop_free(p
->nexthop
);
188 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
191 int vertex_parent_cmp(void *aa
, void *bb
)
193 struct vertex_parent
*a
= aa
, *b
= bb
;
194 return IPV4_ADDR_CMP(&a
->nexthop
->router
, &b
->nexthop
->router
);
197 static struct vertex
*ospf_vertex_new(struct ospf_area
*area
,
198 struct ospf_lsa
*lsa
)
202 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
205 new->type
= lsa
->data
->type
;
206 new->id
= lsa
->data
->id
;
207 new->lsa
= lsa
->data
;
208 new->children
= list_new();
209 new->parents
= list_new();
210 new->parents
->del
= (void (*)(void *))vertex_parent_free
;
211 new->parents
->cmp
= vertex_parent_cmp
;
216 listnode_add(area
->spf_vertex_list
, new);
218 if (IS_DEBUG_OSPF_EVENT
)
219 zlog_debug("%s: Created %s vertex %pI4", __func__
,
220 new->type
== OSPF_VERTEX_ROUTER
? "Router"
227 static void ospf_vertex_free(void *data
)
229 struct vertex
*v
= data
;
231 if (IS_DEBUG_OSPF_EVENT
)
232 zlog_debug("%s: Free %s vertex %pI4", __func__
,
233 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
237 list_delete(&v
->children
);
240 list_delete(&v
->parents
);
244 XFREE(MTYPE_OSPF_VERTEX
, v
);
247 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
248 int print_parents
, int print_children
)
250 if (!IS_DEBUG_OSPF_EVENT
)
253 zlog_debug("%s %s vertex %pI4 distance %u flags %u", msg
,
254 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
255 &v
->lsa
->id
, v
->distance
, (unsigned int)v
->flags
);
258 struct listnode
*node
;
259 struct vertex_parent
*vp
;
261 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
264 "parent %pI4 backlink %d nexthop %pI4 lsa pos %d",
265 &vp
->parent
->lsa
->id
, vp
->backlink
,
266 &vp
->nexthop
->router
,
267 vp
->nexthop
->lsa_pos
);
272 if (print_children
) {
273 struct listnode
*cnode
;
276 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
277 ospf_vertex_dump(" child:", cv
, 0, 0);
282 /* Add a vertex to the list of children in each of its parents. */
283 static void ospf_vertex_add_parent(struct vertex
*v
)
285 struct vertex_parent
*vp
;
286 struct listnode
*node
;
288 assert(v
&& v
->parents
);
290 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
291 assert(vp
->parent
&& vp
->parent
->children
);
293 /* No need to add two links from the same parent. */
294 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
295 listnode_add(vp
->parent
->children
, v
);
299 /* Find a vertex according to its router id */
300 struct vertex
*ospf_spf_vertex_find(struct in_addr id
, struct list
*vertex_list
)
302 struct listnode
*node
;
303 struct vertex
*found
;
305 for (ALL_LIST_ELEMENTS_RO(vertex_list
, node
, found
)) {
306 if (found
->id
.s_addr
== id
.s_addr
)
313 /* Find a vertex parent according to its router id */
314 struct vertex_parent
*ospf_spf_vertex_parent_find(struct in_addr id
,
315 struct vertex
*vertex
)
317 struct listnode
*node
;
318 struct vertex_parent
*found
;
320 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, found
)) {
321 if (found
->parent
->id
.s_addr
== id
.s_addr
)
328 struct vertex
*ospf_spf_vertex_by_nexthop(struct vertex
*root
,
329 struct in_addr
*nexthop
)
331 struct listnode
*node
;
332 struct vertex
*child
;
333 struct vertex_parent
*vertex_parent
;
335 for (ALL_LIST_ELEMENTS_RO(root
->children
, node
, child
)) {
336 vertex_parent
= ospf_spf_vertex_parent_find(root
->id
, child
);
337 if (vertex_parent
->nexthop
->router
.s_addr
== nexthop
->s_addr
)
344 /* Create a deep copy of a SPF vertex without children and parents */
345 static struct vertex
*ospf_spf_vertex_copy(struct vertex
*vertex
)
349 copy
= XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
351 memcpy(copy
, vertex
, sizeof(struct vertex
));
352 copy
->parents
= list_new();
353 copy
->parents
->del
= (void (*)(void *))vertex_parent_free
;
354 copy
->parents
->cmp
= vertex_parent_cmp
;
355 copy
->children
= list_new();
360 /* Create a deep copy of a SPF vertex_parent */
361 static struct vertex_parent
*
362 ospf_spf_vertex_parent_copy(struct vertex_parent
*vertex_parent
)
364 struct vertex_parent
*vertex_parent_copy
;
365 struct vertex_nexthop
*nexthop_copy
, *local_nexthop_copy
;
368 XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex_parent
));
370 nexthop_copy
= vertex_nexthop_new();
371 local_nexthop_copy
= vertex_nexthop_new();
373 memcpy(vertex_parent_copy
, vertex_parent
, sizeof(struct vertex_parent
));
374 memcpy(nexthop_copy
, vertex_parent
->nexthop
,
375 sizeof(struct vertex_nexthop
));
376 memcpy(local_nexthop_copy
, vertex_parent
->local_nexthop
,
377 sizeof(struct vertex_nexthop
));
379 vertex_parent_copy
->nexthop
= nexthop_copy
;
380 vertex_parent_copy
->local_nexthop
= local_nexthop_copy
;
382 return vertex_parent_copy
;
385 /* Create a deep copy of a SPF tree */
386 void ospf_spf_copy(struct vertex
*vertex
, struct list
*vertex_list
)
388 struct listnode
*node
;
389 struct vertex
*vertex_copy
, *child
, *child_copy
, *parent_copy
;
390 struct vertex_parent
*vertex_parent
, *vertex_parent_copy
;
392 /* First check if the node is already in the vertex list */
393 vertex_copy
= ospf_spf_vertex_find(vertex
->id
, vertex_list
);
395 vertex_copy
= ospf_spf_vertex_copy(vertex
);
396 listnode_add(vertex_list
, vertex_copy
);
399 /* Copy all parents, create parent nodes if necessary */
400 for (ALL_LIST_ELEMENTS_RO(vertex
->parents
, node
, vertex_parent
)) {
401 parent_copy
= ospf_spf_vertex_find(vertex_parent
->parent
->id
,
405 ospf_spf_vertex_copy(vertex_parent
->parent
);
406 listnode_add(vertex_list
, parent_copy
);
408 vertex_parent_copy
= ospf_spf_vertex_parent_copy(vertex_parent
);
409 vertex_parent_copy
->parent
= parent_copy
;
410 listnode_add(vertex_copy
->parents
, vertex_parent_copy
);
413 /* Copy all children, create child nodes if necessary */
414 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
415 child_copy
= ospf_spf_vertex_find(child
->id
, vertex_list
);
417 child_copy
= ospf_spf_vertex_copy(child
);
418 listnode_add(vertex_list
, child_copy
);
420 listnode_add(vertex_copy
->children
, child_copy
);
423 /* Finally continue copying with child nodes */
424 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
))
425 ospf_spf_copy(child
, vertex_list
);
428 static void ospf_spf_remove_branch(struct vertex_parent
*vertex_parent
,
429 struct vertex
*child
,
430 struct list
*vertex_list
)
432 struct listnode
*node
, *nnode
, *inner_node
, *inner_nnode
;
433 struct vertex
*grandchild
;
434 struct vertex_parent
*vertex_parent_found
;
435 bool has_more_links
= false;
438 * First check if there are more nexthops for that parent to that child
440 for (ALL_LIST_ELEMENTS_RO(child
->parents
, node
, vertex_parent_found
)) {
441 if (vertex_parent_found
->parent
->id
.s_addr
442 == vertex_parent
->parent
->id
.s_addr
443 && vertex_parent_found
->nexthop
->router
.s_addr
444 != vertex_parent
->nexthop
->router
.s_addr
)
445 has_more_links
= true;
449 * No more links from that parent? Then delete the child from its
453 listnode_delete(vertex_parent
->parent
->children
, child
);
456 * Delete the vertex_parent from the child parents list, this needs to
459 listnode_delete(child
->parents
, vertex_parent
);
462 * Are there actually more parents left? If not, then delete the child!
463 * This is done by recursively removing the links to the grandchildren,
464 * such that finally the child can be removed without leaving unused
467 if (child
->parents
->count
== 0) {
468 for (ALL_LIST_ELEMENTS(child
->children
, node
, nnode
,
470 for (ALL_LIST_ELEMENTS(grandchild
->parents
, inner_node
,
472 vertex_parent_found
)) {
473 ospf_spf_remove_branch(vertex_parent_found
,
474 grandchild
, vertex_list
);
477 listnode_delete(vertex_list
, child
);
478 ospf_vertex_free(child
);
482 static int ospf_spf_remove_link(struct vertex
*vertex
, struct list
*vertex_list
,
483 struct router_lsa_link
*link
)
485 struct listnode
*node
, *inner_node
;
486 struct vertex
*child
;
487 struct vertex_parent
*vertex_parent
;
490 * Identify the node who shares a subnet (given by the link) with a
491 * child and remove the branch of this particular child.
493 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
494 for (ALL_LIST_ELEMENTS_RO(child
->parents
, inner_node
,
496 if ((vertex_parent
->local_nexthop
->router
.s_addr
497 & link
->link_data
.s_addr
)
498 == (link
->link_id
.s_addr
499 & link
->link_data
.s_addr
)) {
500 ospf_spf_remove_branch(vertex_parent
, child
,
507 /* No link found yet, move on recursively */
508 for (ALL_LIST_ELEMENTS_RO(vertex
->children
, node
, child
)) {
509 if (ospf_spf_remove_link(child
, vertex_list
, link
) == 0)
513 /* link was not removed yet */
517 void ospf_spf_remove_resource(struct vertex
*vertex
, struct list
*vertex_list
,
518 struct protected_resource
*resource
)
520 struct listnode
*node
, *nnode
;
521 struct vertex
*found
;
522 struct vertex_parent
*vertex_parent
;
524 switch (resource
->type
) {
525 case OSPF_TI_LFA_LINK_PROTECTION
:
526 ospf_spf_remove_link(vertex
, vertex_list
, resource
->link
);
528 case OSPF_TI_LFA_NODE_PROTECTION
:
529 found
= ospf_spf_vertex_find(resource
->router_id
, vertex_list
);
534 * Remove the node by removing all links from its parents. Note
535 * that the child is automatically removed here with the last
536 * link from a parent, hence no explicit removal of the node.
538 for (ALL_LIST_ELEMENTS(found
->parents
, node
, nnode
,
540 ospf_spf_remove_branch(vertex_parent
, found
,
550 static void ospf_spf_init(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
551 bool is_dry_run
, bool is_root_node
)
553 struct list
*vertex_list
;
556 /* Create vertex list */
557 vertex_list
= list_new();
558 vertex_list
->del
= ospf_vertex_free
;
559 area
->spf_vertex_list
= vertex_list
;
561 /* Create root node. */
562 v
= ospf_vertex_new(area
, root_lsa
);
565 area
->spf_dry_run
= is_dry_run
;
566 area
->spf_root_node
= is_root_node
;
568 /* Reset ABR and ASBR router counts. */
570 area
->asbr_count
= 0;
573 /* return index of link back to V from W, or -1 if no link found */
574 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
576 unsigned int i
, length
;
577 struct router_lsa
*rl
;
578 struct network_lsa
*nl
;
580 /* In case of W is Network LSA. */
581 if (w
->type
== OSPF_NETWORK_LSA
) {
582 if (v
->type
== OSPF_NETWORK_LSA
)
585 nl
= (struct network_lsa
*)w
;
586 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
588 for (i
= 0; i
< length
; i
++)
589 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
594 /* In case of W is Router LSA. */
595 if (w
->type
== OSPF_ROUTER_LSA
) {
596 rl
= (struct router_lsa
*)w
;
598 length
= ntohs(w
->length
);
600 for (i
= 0; i
< ntohs(rl
->links
)
601 && length
>= sizeof(struct router_lsa
);
603 switch (rl
->link
[i
].type
) {
604 case LSA_LINK_TYPE_POINTOPOINT
:
605 case LSA_LINK_TYPE_VIRTUALLINK
:
607 if (v
->type
== OSPF_ROUTER_LSA
608 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
613 case LSA_LINK_TYPE_TRANSIT
:
614 /* Network LSA ID. */
615 if (v
->type
== OSPF_NETWORK_LSA
616 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
621 case LSA_LINK_TYPE_STUB
:
622 /* Stub can't lead anywhere, carry on */
633 * Find the next link after prev_link from v to w. If prev_link is
634 * NULL, return the first link from v to w. Ignore stub and virtual links;
635 * these link types will never be returned.
637 static struct router_lsa_link
*
638 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
639 struct router_lsa_link
*prev_link
)
643 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
644 struct router_lsa_link
*l
;
646 if (w
->type
== OSPF_VERTEX_ROUTER
)
647 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
649 if (prev_link
== NULL
)
650 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
652 p
= (uint8_t *)prev_link
;
653 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
654 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
657 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
660 l
= (struct router_lsa_link
*)p
;
662 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
663 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
665 if (l
->m
[0].type
!= lsa_type
)
668 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
675 static void ospf_spf_flush_parents(struct vertex
*w
)
677 struct vertex_parent
*vp
;
678 struct listnode
*ln
, *nn
;
680 /* delete the existing nexthops */
681 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
682 list_delete_node(w
->parents
, ln
);
683 vertex_parent_free(vp
);
688 * Consider supplied next-hop for inclusion to the supplied list of
689 * equal-cost next-hops, adjust list as necessary.
691 * Returns vertex parent pointer if created otherwise `NULL` if it already
694 static struct vertex_parent
*ospf_spf_add_parent(struct vertex
*v
,
696 struct vertex_nexthop
*newhop
,
697 struct vertex_nexthop
*newlhop
,
698 unsigned int distance
)
700 struct vertex_parent
*vp
, *wp
;
701 struct listnode
*node
;
703 /* we must have a newhop, and a distance */
704 assert(v
&& w
&& newhop
);
708 * IFF w has already been assigned a distance, then we shouldn't get
709 * here unless callers have determined V(l)->W is shortest /
710 * equal-shortest path (0 is a special case distance (no distance yet
714 assert(distance
<= w
->distance
);
716 w
->distance
= distance
;
718 if (IS_DEBUG_OSPF_EVENT
)
719 zlog_debug("%s: Adding %pI4 as parent of %pI4", __func__
,
720 &v
->lsa
->id
, &w
->lsa
->id
);
723 * Adding parent for a new, better path: flush existing parents from W.
725 if (distance
< w
->distance
) {
726 if (IS_DEBUG_OSPF_EVENT
)
728 "%s: distance %d better than %d, flushing existing parents",
729 __func__
, distance
, w
->distance
);
730 ospf_spf_flush_parents(w
);
731 w
->distance
= distance
;
735 * new parent is <= existing parents, add it to parent list (if nexthop
736 * not on parent list)
738 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
739 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
740 if (IS_DEBUG_OSPF_EVENT
)
742 "%s: ... nexthop already on parent list, skipping add",
749 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
,
751 listnode_add_sort(w
->parents
, vp
);
756 static int match_stub_prefix(struct lsa_header
*lsa
, struct in_addr v_link_addr
,
757 struct in_addr w_link_addr
)
760 struct router_lsa_link
*l
= NULL
;
761 struct in_addr masked_lsa_addr
;
763 if (lsa
->type
!= OSPF_ROUTER_LSA
)
766 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
767 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
770 l
= (struct router_lsa_link
*)p
;
771 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
772 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
774 if (l
->m
[0].type
!= LSA_LINK_TYPE_STUB
)
777 masked_lsa_addr
.s_addr
=
778 (l
->link_id
.s_addr
& l
->link_data
.s_addr
);
780 /* check that both links belong to the same stub subnet */
781 if ((masked_lsa_addr
.s_addr
782 == (v_link_addr
.s_addr
& l
->link_data
.s_addr
))
783 && (masked_lsa_addr
.s_addr
784 == (w_link_addr
.s_addr
& l
->link_data
.s_addr
)))
792 * 16.1.1. Calculate nexthop from root through V (parent) to
793 * vertex W (destination), with given distance from root->W.
795 * The link must be supplied if V is the root vertex. In all other cases
798 * Note that this function may fail, hence the state of the destination
799 * vertex, W, should /not/ be modified in a dependent manner until
800 * this function returns. This function will update the W vertex with the
801 * provided distance as appropriate.
803 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
804 struct vertex
*v
, struct vertex
*w
,
805 struct router_lsa_link
*l
,
806 unsigned int distance
, int lsa_pos
)
808 struct listnode
*node
, *nnode
;
809 struct vertex_nexthop
*nh
, *lnh
;
810 struct vertex_parent
*vp
;
811 unsigned int added
= 0;
813 if (IS_DEBUG_OSPF_EVENT
) {
814 zlog_debug("%s: Start", __func__
);
815 ospf_vertex_dump("V (parent):", v
, 1, 1);
816 ospf_vertex_dump("W (dest) :", w
, 1, 1);
817 zlog_debug("V->W distance: %d", distance
);
820 if (v
== area
->spf
) {
822 * 16.1.1 para 4. In the first case, the parent vertex (V) is
823 * the root (the calculating router itself). This means that
824 * the destination is either a directly connected network or
825 * directly connected router. The outgoing interface in this
826 * case is simply the OSPF interface connecting to the
827 * destination network/router.
830 /* we *must* be supplied with the link data */
833 if (IS_DEBUG_OSPF_EVENT
)
835 "%s: considering link type:%d link_id:%pI4 link_data:%pI4",
836 __func__
, l
->m
[0].type
, &l
->link_id
,
839 if (w
->type
== OSPF_VERTEX_ROUTER
) {
841 * l is a link from v to w l2 will be link from w to v
843 struct router_lsa_link
*l2
= NULL
;
845 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
846 struct ospf_interface
*oi
= NULL
;
847 struct in_addr nexthop
= {.s_addr
= 0};
849 if (area
->spf_root_node
) {
850 oi
= ospf_if_lookup_by_lsa_pos(area
,
854 "%s: OI not found in LSA: lsa_pos: %d link_id:%pI4 link_data:%pI4",
863 * If the destination is a router which connects
864 * to the calculating router via a
865 * Point-to-MultiPoint network, the
866 * destination's next hop IP address(es) can be
867 * determined by examining the destination's
868 * router-LSA: each link pointing back to the
869 * calculating router and having a Link Data
870 * field belonging to the Point-to-MultiPoint
871 * network provides an IP address of the next
874 * At this point l is a link from V to W, and V
875 * is the root ("us"). If it is a point-to-
876 * multipoint interface, then look through the
877 * links in the opposite direction (W to V).
878 * If any of them have an address that lands
879 * within the subnet declared by the PtMP link,
880 * then that link is a constituent of the PtMP
881 * link, and its address is a nexthop address
884 * Note for point-to-point interfaces:
886 * Having nexthop = 0 (as proposed in the RFC)
887 * is tempting, but NOT acceptable. It breaks
888 * AS-External routes with a forwarding address,
889 * since ospf_ase_complete_direct_routes() will
890 * mistakenly assume we've reached the last hop
891 * and should place the forwarding address as
892 * nexthop. Also, users may configure multi-
893 * access links in p2p mode, so we need the IP
894 * to ARP the nexthop.
896 * If the calculating router is the SPF root
897 * node and the link is P2P then access the
898 * interface information directly. This can be
899 * crucial when e.g. IP unnumbered is used
900 * where 'correct' nexthop information are not
901 * available via Router LSAs.
903 * Otherwise handle P2P and P2MP the same way
904 * as described above using a reverse lookup to
905 * figure out the nexthop.
909 * HACK: we don't know (yet) how to distinguish
910 * between P2P and P2MP interfaces by just
911 * looking at LSAs, which is important for
912 * TI-LFA since you want to do SPF calculations
913 * from the perspective of other nodes. Since
914 * TI-LFA is currently not implemented for P2MP
915 * we just check here if it is enabled and then
916 * blindly assume that P2P is used. Ultimately
917 * the interface code needs to be removed
920 if (area
->ospf
->ti_lfa_enabled
921 || (oi
&& oi
->type
== OSPF_IFTYPE_POINTOPOINT
)
922 || (oi
&& oi
->type
== OSPF_IFTYPE_POINTOMULTIPOINT
923 && oi
->address
->prefixlen
== IPV4_MAX_BITLEN
)) {
924 struct ospf_neighbor
*nbr_w
= NULL
;
926 /* Calculating node is root node, link
928 if (area
->spf_root_node
) {
929 nbr_w
= ospf_nbr_lookup_by_routerid(
930 oi
->nbrs
, &l
->link_id
);
933 nexthop
= nbr_w
->src
;
939 while ((l2
= ospf_get_next_link(
941 if (match_stub_prefix(
952 } else if (oi
&& oi
->type
953 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
954 struct prefix_ipv4 la
;
957 la
.prefixlen
= oi
->address
->prefixlen
;
960 * V links to W on PtMP interface;
961 * find the interface address on W
963 while ((l2
= ospf_get_next_link(w
, v
,
965 la
.prefix
= l2
->link_data
;
967 if (prefix_cmp((struct prefix
973 nexthop
= l2
->link_data
;
979 nh
= vertex_nexthop_new();
980 nh
->router
= nexthop
;
981 nh
->lsa_pos
= lsa_pos
;
984 * Since v is the root the nexthop and
985 * local nexthop are the same.
987 lnh
= vertex_nexthop_new();
989 sizeof(struct vertex_nexthop
));
991 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
994 vertex_nexthop_free(nh
);
995 vertex_nexthop_free(lnh
);
1000 "%s: could not determine nexthop for link %s",
1001 __func__
, oi
? oi
->ifp
->name
: "");
1002 } /* end point-to-point link from V to W */
1003 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
1005 * VLink implementation limitations:
1006 * a) vl_data can only reference one nexthop,
1007 * so no ECMP to backbone through VLinks.
1008 * Though transit-area summaries may be
1009 * considered, and those can be ECMP.
1010 * b) We can only use /one/ VLink, even if
1011 * multiple ones exist this router through
1012 * multiple transit-areas.
1015 struct ospf_vl_data
*vl_data
;
1017 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
1021 && CHECK_FLAG(vl_data
->flags
,
1022 OSPF_VL_FLAG_APPROVED
)) {
1023 nh
= vertex_nexthop_new();
1024 nh
->router
= vl_data
->nexthop
.router
;
1025 nh
->lsa_pos
= vl_data
->nexthop
.lsa_pos
;
1028 * Since v is the root the nexthop and
1029 * local nexthop are the same.
1031 lnh
= vertex_nexthop_new();
1033 sizeof(struct vertex_nexthop
));
1035 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
1038 vertex_nexthop_free(nh
);
1039 vertex_nexthop_free(lnh
);
1045 "%s: vl_data for VL link not found",
1047 } /* end virtual-link from V to W */
1049 } /* end W is a Router vertex */
1051 assert(w
->type
== OSPF_VERTEX_NETWORK
);
1053 nh
= vertex_nexthop_new();
1054 nh
->router
.s_addr
= 0; /* Nexthop not required */
1055 nh
->lsa_pos
= lsa_pos
;
1058 * Since v is the root the nexthop and
1059 * local nexthop are the same.
1061 lnh
= vertex_nexthop_new();
1062 memcpy(lnh
, nh
, sizeof(struct vertex_nexthop
));
1064 if (ospf_spf_add_parent(v
, w
, nh
, lnh
, distance
) ==
1066 vertex_nexthop_free(nh
);
1067 vertex_nexthop_free(lnh
);
1072 } /* end V is the root */
1073 /* Check if W's parent is a network connected to root. */
1074 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
1075 /* See if any of V's parents are the root. */
1076 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1077 if (vp
->parent
== area
->spf
) {
1079 * 16.1.1 para 5. ...the parent vertex is a
1080 * network that directly connects the
1081 * calculating router to the destination
1082 * router. The list of next hops is then
1083 * determined by examining the destination's
1087 assert(w
->type
== OSPF_VERTEX_ROUTER
);
1088 while ((l
= ospf_get_next_link(w
, v
, l
))) {
1090 * ... For each link in the router-LSA
1091 * that points back to the parent
1092 * network, the link's Link Data field
1093 * provides the IP address of a next hop
1094 * router. The outgoing interface to use
1095 * can then be derived from the next
1096 * hop IP address (or it can be
1097 * inherited from the parent network).
1099 nh
= vertex_nexthop_new();
1100 nh
->router
= l
->link_data
;
1101 nh
->lsa_pos
= vp
->nexthop
->lsa_pos
;
1104 * Since v is the root the nexthop and
1105 * local nexthop are the same.
1107 lnh
= vertex_nexthop_new();
1109 sizeof(struct vertex_nexthop
));
1112 if (ospf_spf_add_parent(v
, w
, nh
, lnh
,
1115 vertex_nexthop_free(nh
);
1116 vertex_nexthop_free(lnh
);
1120 * Note lack of return is deliberate. See next
1126 * NB: This code is non-trivial.
1128 * E.g. it is not enough to know that V connects to the root. It
1129 * is also important that the while above, looping through all
1130 * links from W->V found at least one link, so that we know
1131 * there is bi-directional connectivity between V and W (which
1132 * need not be the case, e.g. when OSPF has not yet converged
1133 * fully). Otherwise, if we /always/ return here, without having
1134 * checked that root->V->-W actually resulted in a valid nexthop
1135 * being created, then we we will prevent SPF from finding/using
1136 * higher cost paths.
1138 * It is important, if root->V->W has not been added, that we
1139 * continue through to the intervening-router nexthop code
1140 * below. So as to ensure other paths to V may be used. This
1141 * avoids unnecessary blackholes while OSPF is converging.
1143 * I.e. we may have arrived at this function, examining V -> W,
1144 * via workable paths other than root -> V, and it's important
1145 * to avoid getting "confused" by non-working root->V->W path
1146 * - it's important to *not* lose the working non-root paths,
1147 * just because of a non-viable root->V->W.
1154 * 16.1.1 para 4. If there is at least one intervening router in the
1155 * current shortest path between the destination and the root, the
1156 * destination simply inherits the set of next hops from the
1159 if (IS_DEBUG_OSPF_EVENT
)
1160 zlog_debug("%s: Intervening routers, adding parent(s)",
1163 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
1167 * The nexthop is inherited, but the local nexthop still needs
1171 lnh
= vertex_nexthop_new();
1172 lnh
->router
= l
->link_data
;
1173 lnh
->lsa_pos
= lsa_pos
;
1178 nh
= vertex_nexthop_new();
1181 if (ospf_spf_add_parent(v
, w
, nh
, lnh
, distance
) == NULL
) {
1182 vertex_nexthop_free(nh
);
1183 vertex_nexthop_free(lnh
);
1190 static int ospf_spf_is_protected_resource(struct ospf_area
*area
,
1191 struct router_lsa_link
*link
,
1192 struct lsa_header
*lsa
)
1195 struct router_lsa_link
*p_link
;
1196 struct router_lsa_link
*l
= NULL
;
1197 struct in_addr router_id
;
1200 if (!area
->spf_protected_resource
)
1203 link_type
= link
->m
[0].type
;
1205 switch (area
->spf_protected_resource
->type
) {
1206 case OSPF_TI_LFA_LINK_PROTECTION
:
1207 p_link
= area
->spf_protected_resource
->link
;
1211 /* For P2P: check if the link belongs to the same subnet */
1212 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1213 && (p_link
->link_id
.s_addr
& p_link
->link_data
.s_addr
)
1214 == (link
->link_data
.s_addr
1215 & p_link
->link_data
.s_addr
))
1218 /* For stub: check if this the same subnet */
1219 if (link_type
== LSA_LINK_TYPE_STUB
1220 && (p_link
->link_id
.s_addr
== link
->link_id
.s_addr
)
1221 && (p_link
->link_data
.s_addr
== link
->link_data
.s_addr
))
1225 case OSPF_TI_LFA_NODE_PROTECTION
:
1226 router_id
= area
->spf_protected_resource
->router_id
;
1227 if (router_id
.s_addr
== INADDR_ANY
)
1230 /* For P2P: check if the link leads to the protected node */
1231 if (link_type
== LSA_LINK_TYPE_POINTOPOINT
1232 && link
->link_id
.s_addr
== router_id
.s_addr
)
1235 /* The rest is about stub links! */
1236 if (link_type
!= LSA_LINK_TYPE_STUB
)
1240 * Check if there's a P2P link in the router LSA with the
1241 * corresponding link data in the same subnet.
1244 p
= ((uint8_t *)lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1245 lim
= ((uint8_t *)lsa
) + ntohs(lsa
->length
);
1248 l
= (struct router_lsa_link
*)p
;
1249 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1250 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1252 /* We only care about P2P with the proper link id */
1253 if ((l
->m
[0].type
!= LSA_LINK_TYPE_POINTOPOINT
)
1254 || (l
->link_id
.s_addr
!= router_id
.s_addr
))
1257 /* Link data in the subnet given by the link? */
1258 if ((link
->link_id
.s_addr
& link
->link_data
.s_addr
)
1259 == (l
->link_data
.s_addr
& link
->link_data
.s_addr
))
1264 case OSPF_TI_LFA_UNDEFINED_PROTECTION
:
1272 * For TI-LFA we need the reverse SPF for Q spaces. The reverse SPF is created
1273 * by honoring the weight of the reverse 'edge', e.g. the edge from W to V, and
1274 * NOT the weight of the 'edge' from V to W as usual. Hence we need to find the
1275 * corresponding link in the LSA of W and extract the particular weight.
1277 * TODO: Only P2P supported by now!
1279 static uint16_t get_reverse_distance(struct vertex
*v
,
1280 struct router_lsa_link
*l
,
1281 struct ospf_lsa
*w_lsa
)
1284 struct router_lsa_link
*w_link
;
1285 uint16_t distance
= 0;
1287 assert(w_lsa
&& w_lsa
->data
);
1289 p
= ((uint8_t *)w_lsa
->data
) + OSPF_LSA_HEADER_SIZE
+ 4;
1290 lim
= ((uint8_t *)w_lsa
->data
) + ntohs(w_lsa
->data
->length
);
1293 w_link
= (struct router_lsa_link
*)p
;
1294 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1295 + (w_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1297 /* Only care about P2P with link ID equal to V's router id */
1298 if (w_link
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
1299 && w_link
->link_id
.s_addr
== v
->id
.s_addr
) {
1300 distance
= ntohs(w_link
->m
[0].metric
);
1306 * This might happen if the LSA for W is not complete yet. In this
1307 * case we take the weight of the 'forward' link from V. When the LSA
1308 * for W is completed the reverse SPF is run again anyway.
1311 distance
= ntohs(l
->m
[0].metric
);
1313 if (IS_DEBUG_OSPF_EVENT
)
1314 zlog_debug("%s: reversed distance is %u", __func__
, distance
);
1321 * v is on the SPF tree. Examine the links in v's LSA. Update the list of
1322 * candidates with any vertices not already on the list. If a lower-cost path
1323 * is found to a vertex already on the candidate list, store the new cost.
1325 static void ospf_spf_next(struct vertex
*v
, struct ospf_area
*area
,
1326 struct vertex_pqueue_head
*candidate
)
1328 struct ospf_lsa
*w_lsa
= NULL
;
1331 struct router_lsa_link
*l
= NULL
;
1333 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
1334 uint16_t link_distance
;
1337 * If this is a router-LSA, and bit V of the router-LSA (see Section
1338 * A.4.2:RFC2328) is set, set Area A's TransitCapability to true.
1340 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1341 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
1342 area
->transit
= OSPF_TRANSIT_TRUE
;
1345 if (IS_DEBUG_OSPF_EVENT
)
1346 zlog_debug("%s: Next vertex of %s vertex %pI4", __func__
,
1347 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
1350 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1351 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1355 unsigned int distance
;
1357 /* In case of V is Router-LSA. */
1358 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
1359 l
= (struct router_lsa_link
*)p
;
1361 lsa_pos
= lsa_pos_next
; /* LSA link position */
1364 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1365 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1368 * (a) If this is a link to a stub network, examine the
1369 * next link in V's LSA. Links to stub networks will
1370 * be considered in the second stage of the shortest
1373 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
1377 * Don't process TI-LFA protected resources.
1379 * TODO: Replace this by a proper solution, e.g. remove
1380 * corresponding links from the LSDB and run the SPF
1381 * algo with the stripped-down LSDB.
1383 if (ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1387 * (b) Otherwise, W is a transit vertex (router or
1388 * transit network). Look up the vertex W's LSA
1389 * (router-LSA or network-LSA) in Area A's link state
1393 case LSA_LINK_TYPE_POINTOPOINT
:
1394 case LSA_LINK_TYPE_VIRTUALLINK
:
1395 if (type
== LSA_LINK_TYPE_VIRTUALLINK
1396 && IS_DEBUG_OSPF_EVENT
)
1398 "looking up LSA through VL: %pI4",
1400 w_lsa
= ospf_lsa_lookup(area
->ospf
, area
,
1402 l
->link_id
, l
->link_id
);
1403 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1404 zlog_debug("found Router LSA %pI4",
1407 case LSA_LINK_TYPE_TRANSIT
:
1408 if (IS_DEBUG_OSPF_EVENT
)
1410 "Looking up Network LSA, ID: %pI4",
1412 w_lsa
= ospf_lsa_lookup_by_id(
1413 area
, OSPF_NETWORK_LSA
, l
->link_id
);
1414 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1415 zlog_debug("found the LSA");
1418 flog_warn(EC_OSPF_LSA
,
1419 "Invalid LSA link type %d", type
);
1424 * For TI-LFA we might need the reverse SPF.
1425 * Currently only works with P2P!
1427 if (type
== LSA_LINK_TYPE_POINTOPOINT
1428 && area
->spf_reversed
)
1430 get_reverse_distance(v
, l
, w_lsa
);
1432 link_distance
= ntohs(l
->m
[0].metric
);
1434 /* step (d) below */
1435 distance
= v
->distance
+ link_distance
;
1437 /* In case of V is Network-LSA. */
1438 r
= (struct in_addr
*)p
;
1439 p
+= sizeof(struct in_addr
);
1441 /* Lookup the vertex W's LSA. */
1442 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
1444 if (w_lsa
&& IS_DEBUG_OSPF_EVENT
)
1445 zlog_debug("found Router LSA %pI4",
1448 /* step (d) below */
1449 distance
= v
->distance
;
1453 * (b cont.) If the LSA does not exist, or its LS age is equal
1454 * to MaxAge, or it does not have a link back to vertex V,
1455 * examine the next link in V's LSA.[23]
1457 if (w_lsa
== NULL
) {
1458 if (IS_DEBUG_OSPF_EVENT
)
1459 zlog_debug("No LSA found");
1463 if (IS_LSA_MAXAGE(w_lsa
)) {
1464 if (IS_DEBUG_OSPF_EVENT
)
1465 zlog_debug("LSA is MaxAge");
1469 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
1470 if (IS_DEBUG_OSPF_EVENT
)
1471 zlog_debug("The LSA doesn't have a link back");
1476 * (c) If vertex W is already on the shortest-path tree, examine
1477 * the next link in the LSA.
1479 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
1480 if (IS_DEBUG_OSPF_EVENT
)
1481 zlog_debug("The LSA is already in SPF");
1486 * (d) Calculate the link state cost D of the resulting path
1487 * from the root to vertex W. D is equal to the sum of the link
1488 * state cost of the (already calculated) shortest path to
1489 * vertex V and the advertised cost of the link between vertices
1493 /* calculate link cost D -- moved above */
1495 /* Is there already vertex W in candidate list? */
1496 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
1497 /* prepare vertex W. */
1498 w
= ospf_vertex_new(area
, w_lsa
);
1500 /* Calculate nexthop to W. */
1501 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
1503 vertex_pqueue_add(candidate
, w
);
1505 listnode_delete(area
->spf_vertex_list
, w
);
1506 ospf_vertex_free(w
);
1507 w_lsa
->stat
= LSA_SPF_NOT_EXPLORED
;
1508 if (IS_DEBUG_OSPF_EVENT
)
1509 zlog_debug("Nexthop Calc failed");
1511 } else if (w_lsa
->stat
!= LSA_SPF_IN_SPFTREE
) {
1513 if (w
->distance
< distance
) {
1516 else if (w
->distance
== distance
) {
1518 * Found an equal-cost path to W.
1519 * Calculate nexthop of to W from V.
1521 ospf_nexthop_calculation(area
, v
, w
, l
,
1526 * Found a lower-cost path to W.
1527 * nexthop_calculation is conditional, if it
1528 * finds valid nexthop it will call
1529 * spf_add_parents, which will flush the old
1532 vertex_pqueue_del(candidate
, w
);
1533 ospf_nexthop_calculation(area
, v
, w
, l
,
1535 vertex_pqueue_add(candidate
, w
);
1537 } /* end W is already on the candidate list */
1538 } /* end loop over the links in V's LSA */
1541 static void ospf_spf_dump(struct vertex
*v
, int i
)
1543 struct listnode
*cnode
;
1544 struct listnode
*nnode
;
1545 struct vertex_parent
*parent
;
1547 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1548 if (IS_DEBUG_OSPF_EVENT
)
1549 zlog_debug("SPF Result: %d [R] %pI4", i
,
1552 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1553 if (IS_DEBUG_OSPF_EVENT
)
1554 zlog_debug("SPF Result: %d [N] %pI4/%d", i
,
1556 ip_masklen(lsa
->mask
));
1559 if (IS_DEBUG_OSPF_EVENT
)
1560 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1561 zlog_debug(" nexthop %p %pI4 %d",
1562 (void *)parent
->nexthop
,
1563 &parent
->nexthop
->router
,
1564 parent
->nexthop
->lsa_pos
);
1569 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1570 ospf_spf_dump(v
, i
);
1573 void ospf_spf_print(struct vty
*vty
, struct vertex
*v
, int i
)
1575 struct listnode
*cnode
;
1576 struct listnode
*nnode
;
1577 struct vertex_parent
*parent
;
1579 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1580 vty_out(vty
, "SPF Result: depth %d [R] %pI4\n", i
, &v
->lsa
->id
);
1582 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
1583 vty_out(vty
, "SPF Result: depth %d [N] %pI4/%d\n", i
,
1584 &v
->lsa
->id
, ip_masklen(lsa
->mask
));
1587 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
1589 " nexthop %pI4 lsa pos %d -- local nexthop %pI4 lsa pos %d\n",
1590 &parent
->nexthop
->router
, parent
->nexthop
->lsa_pos
,
1591 &parent
->local_nexthop
->router
,
1592 parent
->local_nexthop
->lsa_pos
);
1597 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1598 ospf_spf_print(vty
, v
, i
);
1601 /* Second stage of SPF calculation. */
1602 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1603 struct route_table
*rt
, int parent_is_root
)
1605 struct listnode
*cnode
, *cnnode
;
1606 struct vertex
*child
;
1608 if (IS_DEBUG_OSPF_EVENT
)
1609 zlog_debug("%s: processing stubs for area %pI4", __func__
,
1612 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1615 struct router_lsa_link
*l
;
1616 struct router_lsa
*router_lsa
;
1619 if (IS_DEBUG_OSPF_EVENT
)
1620 zlog_debug("%s: processing router LSA, id: %pI4",
1621 __func__
, &v
->lsa
->id
);
1623 router_lsa
= (struct router_lsa
*)v
->lsa
;
1625 if (IS_DEBUG_OSPF_EVENT
)
1626 zlog_debug("%s: we have %d links to process", __func__
,
1627 ntohs(router_lsa
->links
));
1629 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1630 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1633 l
= (struct router_lsa_link
*)p
;
1635 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1636 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1638 /* Don't process TI-LFA protected resources */
1639 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
1640 && !ospf_spf_is_protected_resource(area
, l
, v
->lsa
))
1641 ospf_intra_add_stub(rt
, l
, v
, area
,
1642 parent_is_root
, lsa_pos
);
1647 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1650 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1651 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1655 * The first level of routers connected to the root
1656 * should have 'parent_is_root' set, including those
1657 * connected via a network vertex.
1661 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1664 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1666 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1670 void ospf_rtrs_free(struct route_table
*rtrs
)
1672 struct route_node
*rn
;
1673 struct list
*or_list
;
1674 struct ospf_route
* or ;
1675 struct listnode
*node
, *nnode
;
1677 if (IS_DEBUG_OSPF_EVENT
)
1678 zlog_debug("Route: Router Routing Table free");
1680 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1681 if ((or_list
= rn
->info
) != NULL
) {
1682 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1683 ospf_route_free(or);
1685 list_delete(&or_list
);
1687 /* Unlock the node. */
1689 route_unlock_node(rn
);
1692 route_table_finish(rtrs
);
1695 void ospf_spf_cleanup(struct vertex
*spf
, struct list
*vertex_list
)
1698 * Free nexthop information, canonical versions of which are
1699 * attached the first level of router vertices attached to the
1700 * root vertex, see ospf_nexthop_calculation.
1703 ospf_canonical_nexthops_free(spf
);
1705 /* Free SPF vertices list with deconstructor ospf_vertex_free. */
1707 list_delete(&vertex_list
);
1710 /* Calculating the shortest-path tree for an area, see RFC2328 16.1. */
1711 void ospf_spf_calculate(struct ospf_area
*area
, struct ospf_lsa
*root_lsa
,
1712 struct route_table
*new_table
,
1713 struct route_table
*all_rtrs
,
1714 struct route_table
*new_rtrs
, bool is_dry_run
,
1717 struct vertex_pqueue_head candidate
;
1720 if (IS_DEBUG_OSPF_EVENT
) {
1721 zlog_debug("%s: Start: running Dijkstra for area %pI4",
1722 __func__
, &area
->area_id
);
1726 * If the router LSA of the root is not yet allocated, return this
1727 * area's calculation. In the 'usual' case the root_lsa is the
1728 * self-originated router LSA of the node itself.
1731 if (IS_DEBUG_OSPF_EVENT
)
1733 "%s: Skip area %pI4's calculation due to empty root LSA",
1734 __func__
, &area
->area_id
);
1738 /* Initialize the algorithm's data structures, see RFC2328 16.1. (1). */
1741 * This function scans all the LSA database and set the stat field to
1742 * LSA_SPF_NOT_EXPLORED.
1744 lsdb_clean_stat(area
->lsdb
);
1746 /* Create a new heap for the candidates. */
1747 vertex_pqueue_init(&candidate
);
1750 * Initialize the shortest-path tree to only the root (which is usually
1751 * the router doing the calculation).
1753 ospf_spf_init(area
, root_lsa
, is_dry_run
, is_root_node
);
1755 /* Set Area A's TransitCapability to false. */
1756 area
->transit
= OSPF_TRANSIT_FALSE
;
1757 area
->shortcut_capability
= 1;
1760 * Use the root vertex for the start of the SPF algorithm and make it
1764 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1767 /* RFC2328 16.1. (2). */
1768 ospf_spf_next(v
, area
, &candidate
);
1770 /* RFC2328 16.1. (3). */
1771 v
= vertex_pqueue_pop(&candidate
);
1773 /* No more vertices left. */
1776 v
->lsa_p
->stat
= LSA_SPF_IN_SPFTREE
;
1778 ospf_vertex_add_parent(v
);
1780 /* RFC2328 16.1. (4). */
1781 if (v
->type
!= OSPF_VERTEX_ROUTER
)
1782 ospf_intra_add_transit(new_table
, v
, area
);
1784 ospf_intra_add_router(new_rtrs
, v
, area
, false);
1786 ospf_intra_add_router(all_rtrs
, v
, area
, true);
1789 /* Iterate back to (2), see RFC2328 16.1. (5). */
1792 if (IS_DEBUG_OSPF_EVENT
) {
1793 ospf_spf_dump(area
->spf
, 0);
1794 ospf_route_table_dump(new_table
);
1796 ospf_router_route_table_dump(all_rtrs
);
1800 * Second stage of SPF calculation procedure's, add leaves to the tree
1801 * for stub networks.
1803 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1805 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1807 /* Increment SPF Calculation Counter. */
1808 area
->spf_calculation
++;
1810 monotime(&area
->ospf
->ts_spf
);
1811 area
->ts_spf
= area
->ospf
->ts_spf
;
1813 if (IS_DEBUG_OSPF_EVENT
)
1814 zlog_debug("%s: Stop. %zd vertices", __func__
,
1815 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1818 void ospf_spf_calculate_area(struct ospf
*ospf
, struct ospf_area
*area
,
1819 struct route_table
*new_table
,
1820 struct route_table
*all_rtrs
,
1821 struct route_table
*new_rtrs
)
1823 ospf_spf_calculate(area
, area
->router_lsa_self
, new_table
, all_rtrs
,
1824 new_rtrs
, false, true);
1826 if (ospf
->ti_lfa_enabled
)
1827 ospf_ti_lfa_compute(area
, new_table
,
1828 ospf
->ti_lfa_protection_type
);
1830 ospf_spf_cleanup(area
->spf
, area
->spf_vertex_list
);
1833 area
->spf_vertex_list
= NULL
;
1836 void ospf_spf_calculate_areas(struct ospf
*ospf
, struct route_table
*new_table
,
1837 struct route_table
*all_rtrs
,
1838 struct route_table
*new_rtrs
)
1840 struct ospf_area
*area
;
1841 struct listnode
*node
, *nnode
;
1843 /* Calculate SPF for each area. */
1844 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1845 /* Do backbone last, so as to first discover intra-area paths
1846 * for any back-bone virtual-links */
1847 if (ospf
->backbone
&& ospf
->backbone
== area
)
1850 ospf_spf_calculate_area(ospf
, area
, new_table
, all_rtrs
,
1854 /* SPF for backbone, if required */
1856 ospf_spf_calculate_area(ospf
, ospf
->backbone
, new_table
,
1857 all_rtrs
, new_rtrs
);
1860 /* Print Reason for SPF calculation */
1861 static void ospf_spf_calculation_reason2str(char *rbuf
, size_t len
)
1864 if (spf_reason_flags
) {
1865 if (spf_reason_flags
& (1 << SPF_FLAG_ROUTER_LSA_INSTALL
))
1866 strlcat(rbuf
, "R, ", len
);
1867 if (spf_reason_flags
& (1 << SPF_FLAG_NETWORK_LSA_INSTALL
))
1868 strlcat(rbuf
, "N, ", len
);
1869 if (spf_reason_flags
& (1 << SPF_FLAG_SUMMARY_LSA_INSTALL
))
1870 strlcat(rbuf
, "S, ", len
);
1871 if (spf_reason_flags
& (1 << SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
))
1872 strlcat(rbuf
, "AS, ", len
);
1873 if (spf_reason_flags
& (1 << SPF_FLAG_ABR_STATUS_CHANGE
))
1874 strlcat(rbuf
, "ABR, ", len
);
1875 if (spf_reason_flags
& (1 << SPF_FLAG_ASBR_STATUS_CHANGE
))
1876 strlcat(rbuf
, "ASBR, ", len
);
1877 if (spf_reason_flags
& (1 << SPF_FLAG_MAXAGE
))
1878 strlcat(rbuf
, "M, ", len
);
1879 if (spf_reason_flags
& (1 << SPF_FLAG_ORR_ROOT_CHANGE
))
1880 strlcat(rbuf
, "ORR, ", len
);
1882 size_t rbuflen
= strlen(rbuf
);
1884 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1890 /* Worker for SPF calculation scheduler. */
1891 static void ospf_spf_calculate_schedule_worker(struct thread
*thread
)
1893 struct ospf
*ospf
= THREAD_ARG(thread
);
1894 struct route_table
*new_table
, *new_rtrs
;
1895 struct route_table
*all_rtrs
= NULL
;
1896 struct timeval start_time
, spf_start_time
;
1897 unsigned long ia_time
, prune_time
, rt_time
;
1898 unsigned long abr_time
, total_spf_time
, spf_time
;
1899 char rbuf
[32]; /* reason_buf */
1901 if (IS_DEBUG_OSPF_EVENT
)
1902 zlog_debug("SPF: Timer (SPF calculation expire)");
1904 ospf
->t_spf_calc
= NULL
;
1906 ospf_vl_unapprove(ospf
);
1908 /* Execute SPF for each area including backbone, see RFC 2328 16.1. */
1909 monotime(&spf_start_time
);
1910 new_table
= route_table_init(); /* routing table */
1911 new_rtrs
= route_table_init(); /* ABR/ASBR routing table */
1913 /* If we have opaque enabled then track all router reachability */
1914 if (CHECK_FLAG(ospf
->opaque
, OPAQUE_OPERATION_READY_BIT
))
1915 all_rtrs
= route_table_init();
1917 ospf_spf_calculate_areas(ospf
, new_table
, all_rtrs
, new_rtrs
);
1918 spf_time
= monotime_since(&spf_start_time
, NULL
);
1920 ospf_vl_shut_unapproved(ospf
);
1922 /* Calculate inter-area routes, see RFC 2328 16.2. */
1923 monotime(&start_time
);
1924 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1925 ia_time
= monotime_since(&start_time
, NULL
);
1927 /* Get rid of transit networks and routers we cannot reach anyway. */
1928 monotime(&start_time
);
1929 ospf_prune_unreachable_networks(new_table
);
1931 ospf_prune_unreachable_routers(all_rtrs
);
1932 ospf_prune_unreachable_routers(new_rtrs
);
1933 prune_time
= monotime_since(&start_time
, NULL
);
1935 /* Note: RFC 2328 16.3. is apparently missing. */
1938 * Calculate AS external routes, see RFC 2328 16.4.
1939 * There is a dedicated routing table for external routes which is not
1940 * handled here directly
1942 ospf_ase_calculate_schedule(ospf
);
1943 ospf_ase_calculate_timer_add(ospf
);
1945 ospf_orr_spf_calculate_schedule(ospf
);
1947 if (IS_DEBUG_OSPF_EVENT
)
1949 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1950 __func__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1951 ospf
->vrf_id
, new_table
->count
);
1953 /* Update routing table. */
1954 monotime(&start_time
);
1955 ospf_route_install(ospf
, new_table
);
1956 rt_time
= monotime_since(&start_time
, NULL
);
1958 /* Free old all routers routing table */
1959 if (ospf
->oall_rtrs
) {
1960 ospf_rtrs_free(ospf
->oall_rtrs
);
1961 ospf
->oall_rtrs
= NULL
;
1964 /* Update all routers routing table */
1965 ospf
->oall_rtrs
= ospf
->all_rtrs
;
1966 ospf
->all_rtrs
= all_rtrs
;
1967 #ifdef SUPPORT_OSPF_API
1968 ospf_apiserver_notify_reachable(ospf
->oall_rtrs
, ospf
->all_rtrs
);
1970 /* Free old ABR/ASBR routing table */
1971 if (ospf
->old_rtrs
) {
1972 ospf_rtrs_free(ospf
->old_rtrs
);
1973 ospf
->old_rtrs
= NULL
;
1976 /* Update ABR/ASBR routing table */
1977 ospf
->old_rtrs
= ospf
->new_rtrs
;
1978 ospf
->new_rtrs
= new_rtrs
;
1980 /* ABRs may require additional changes, see RFC 2328 16.7. */
1981 monotime(&start_time
);
1982 if (IS_OSPF_ABR(ospf
)) {
1984 ospf_abr_nssa_check_status(ospf
);
1985 ospf_abr_task(ospf
);
1987 abr_time
= monotime_since(&start_time
, NULL
);
1989 /* Schedule Segment Routing update */
1990 ospf_sr_update_task(ospf
);
1993 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1995 ospf_spf_calculation_reason2str(rbuf
, sizeof(rbuf
));
1997 if (IS_DEBUG_OSPF_EVENT
) {
1998 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1999 zlog_info(" SPF Time: %ld", spf_time
);
2000 zlog_info(" InterArea: %ld", ia_time
);
2001 zlog_info(" Prune: %ld", prune_time
);
2002 zlog_info(" RouteInstall: %ld", rt_time
);
2003 if (IS_OSPF_ABR(ospf
))
2004 zlog_info(" ABR: %ld (%d areas)",
2005 abr_time
, ospf
->areas
->count
);
2006 zlog_info("Reason(s) for SPF: %s", rbuf
);
2009 ospf_clear_spf_reason_flags();
2012 /* Worker for ORR SPF calculation scheduler. */
2013 void ospf_orr_spf_calculate_schedule_worker(struct thread
*thread
)
2017 struct ospf
*ospf
= THREAD_ARG(thread
);
2018 struct route_table
*new_table
, *new_rtrs
;
2019 struct route_table
*all_rtrs
= NULL
;
2020 struct timeval start_time
, spf_start_time
;
2021 unsigned long ia_time
, rt_time
;
2022 unsigned long abr_time
, total_spf_time
, spf_time
;
2023 struct listnode
*rnode
;
2024 struct list
*orr_root_list
;
2025 struct orr_root
*root
;
2026 char rbuf
[32]; /* reason_buf */
2028 ospf_orr_debug("%s: SPF: Timer (SPF calculation expire)", __func__
);
2030 ospf
->t_orr_calc
= NULL
;
2032 /* Execute SPF for each ORR Root node */
2033 FOREACH_AFI_SAFI (afi
, safi
) {
2034 orr_root_list
= ospf
->orr_root
[afi
][safi
];
2037 for (ALL_LIST_ELEMENTS_RO(orr_root_list
, rnode
, root
)) {
2038 if (!root
|| !root
->router_lsa_rcvd
)
2041 "%s: For %s %s, MPLS TE Router address %pI4 advertised by %pI4",
2042 __func__
, afi2str(afi
), safi2str(safi
),
2043 &root
->router_id
, &root
->adv_router
);
2045 ospf_vl_unapprove(ospf
);
2048 * Execute SPF for each area including backbone, see RFC
2051 monotime(&spf_start_time
);
2052 new_table
= route_table_init(); /* routing table */
2054 route_table_init(); /* ABR/ASBR routing table */
2057 * If we have opaque enabled then track all router
2060 if (CHECK_FLAG(ospf
->opaque
,
2061 OPAQUE_OPERATION_READY_BIT
))
2062 all_rtrs
= route_table_init();
2063 ospf_orr_spf_calculate_areas(ospf
, new_table
, all_rtrs
,
2065 root
->router_lsa_rcvd
);
2067 spf_time
= monotime_since(&spf_start_time
, NULL
);
2069 ospf_vl_shut_unapproved(ospf
);
2071 /* Calculate inter-area routes, see RFC 2328 16.2. */
2072 monotime(&start_time
);
2073 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
2074 ia_time
= monotime_since(&start_time
, NULL
);
2078 * Pruning of unreachable networks, routers skipped.
2081 /* Note: RFC 2328 16.3. is apparently missing. */
2082 /* Calculate AS external routes, see RFC 2328 16.4.
2083 * There is a dedicated routing table for external
2084 * routes which is not handled here directly
2086 ospf_ase_calculate_schedule(ospf
);
2087 ospf_ase_calculate_timer_add(ospf
);
2090 "%s: ospf install new route, vrf %s id %u new_table count %lu",
2091 __func__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
2092 ospf
->vrf_id
, new_table
->count
);
2094 /* Update routing table. */
2095 monotime(&start_time
);
2096 ospf_orr_route_install(root
, new_table
, ospf
->instance
);
2097 rt_time
= monotime_since(&start_time
, NULL
);
2101 * Freeing up and Updating old all routers routing table
2105 /* Free old ABR/ASBR routing table */
2107 /* ospf_route_delete (ospf->old_rtrs); */
2108 ospf_rtrs_free(root
->old_rtrs
);
2110 /* Update ABR/ASBR routing table */
2111 root
->old_rtrs
= root
->new_rtrs
;
2112 root
->new_rtrs
= new_rtrs
;
2115 * ABRs may require additional changes, see RFC
2118 monotime(&start_time
);
2119 if (IS_OSPF_ABR(ospf
)) {
2121 ospf_abr_nssa_check_status(ospf
);
2122 ospf_abr_task(ospf
);
2124 abr_time
= monotime_since(&start_time
, NULL
);
2126 /* Schedule Segment Routing update */
2127 ospf_sr_update_task(ospf
);
2129 total_spf_time
= monotime_since(&spf_start_time
,
2130 &ospf
->ts_spf_duration
);
2132 ospf_spf_calculation_reason2str(rbuf
, sizeof(rbuf
));
2134 if (IS_DEBUG_OSPF_ORR
) {
2135 zlog_info("SPF Processing Time(usecs): %ld",
2137 zlog_info(" SPF Time: %ld",
2139 zlog_info(" InterArea: %ld", ia_time
);
2140 zlog_info(" RouteInstall: %ld", rt_time
);
2141 if (IS_OSPF_ABR(ospf
))
2143 " ABR: %ld (%d areas)",
2144 abr_time
, ospf
->areas
->count
);
2145 zlog_info("Reason(s) for SPF: %s", rbuf
);
2147 } /* ALL_LIST_ELEMENTS_RO() */
2148 } /* FOREACH_AFI_SAFI() */
2152 * Add schedule for SPF calculation. To avoid frequenst SPF calc, we set timer
2155 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
2157 unsigned long delay
, elapsed
, ht
;
2159 if (IS_DEBUG_OSPF_EVENT
)
2160 zlog_debug("SPF: calculation timer scheduled");
2162 /* OSPF instance does not exist. */
2166 ospf_spf_set_reason(reason
);
2168 /* SPF calculation timer is already scheduled. */
2169 if (ospf
->t_spf_calc
) {
2170 if (IS_DEBUG_OSPF_EVENT
)
2172 "SPF: calculation timer is already scheduled: %p",
2173 (void *)ospf
->t_spf_calc
);
2177 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
2179 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
2181 if (ht
> ospf
->spf_max_holdtime
)
2182 ht
= ospf
->spf_max_holdtime
;
2184 /* Get SPF calculation delay time. */
2187 * Got an event within the hold time of last SPF. We need to
2188 * increase the hold_multiplier, if it's not already at/past
2189 * maximum value, and wasn't already increased.
2191 if (ht
< ospf
->spf_max_holdtime
)
2192 ospf
->spf_hold_multiplier
++;
2194 /* always honour the SPF initial delay */
2195 if ((ht
- elapsed
) < ospf
->spf_delay
)
2196 delay
= ospf
->spf_delay
;
2198 delay
= ht
- elapsed
;
2200 /* Event is past required hold-time of last SPF */
2201 delay
= ospf
->spf_delay
;
2202 ospf
->spf_hold_multiplier
= 1;
2205 if (IS_DEBUG_OSPF_EVENT
)
2206 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
2208 ospf
->t_spf_calc
= NULL
;
2210 thread_add_timer_msec(master
, ospf_spf_calculate_schedule_worker
, ospf
,
2211 delay
, &ospf
->t_spf_calc
);
2214 /* Restart OSPF SPF algorithm*/
2215 void ospf_restart_spf(struct ospf
*ospf
)
2217 if (IS_DEBUG_OSPF_EVENT
)
2218 zlog_debug("%s: Restart SPF.", __func__
);
2220 /* Handling inter area and intra area routes*/
2221 if (ospf
->new_table
) {
2222 ospf_route_delete(ospf
, ospf
->new_table
);
2223 ospf_route_table_free(ospf
->new_table
);
2224 ospf
->new_table
= route_table_init();
2227 /* Handling of TYPE-5 lsa(external routes) */
2228 if (ospf
->old_external_route
) {
2229 ospf_route_delete(ospf
, ospf
->old_external_route
);
2230 ospf_route_table_free(ospf
->old_external_route
);
2231 ospf
->old_external_route
= route_table_init();
2235 ospf_spf_calculate_schedule(ospf
, SPF_FLAG_CONFIG_CHANGE
);