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 () */
35 #include "ospfd/ospfd.h"
36 #include "ospfd/ospf_interface.h"
37 #include "ospfd/ospf_ism.h"
38 #include "ospfd/ospf_asbr.h"
39 #include "ospfd/ospf_lsa.h"
40 #include "ospfd/ospf_lsdb.h"
41 #include "ospfd/ospf_neighbor.h"
42 #include "ospfd/ospf_nsm.h"
43 #include "ospfd/ospf_spf.h"
44 #include "ospfd/ospf_route.h"
45 #include "ospfd/ospf_ia.h"
46 #include "ospfd/ospf_ase.h"
47 #include "ospfd/ospf_abr.h"
48 #include "ospfd/ospf_dump.h"
49 #include "ospfd/ospf_sr.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 static void ospf_clear_spf_reason_flags(void)
61 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
63 spf_reason_flags
|= 1 << reason
;
66 static void ospf_vertex_free(void *);
67 /* List of allocated vertices, to simplify cleanup of SPF.
68 * Not thread-safe obviously. If it ever needs to be, it'd have to be
69 * dynamically allocated at begin of ospf_spf_calculate
71 static struct list vertex_list
= {.del
= ospf_vertex_free
};
73 /* Heap related functions, for the managment of the candidates, to
74 * be used with pqueue. */
75 static int cmp(void *node1
, void *node2
)
77 struct vertex
*v1
= (struct vertex
*)node1
;
78 struct vertex
*v2
= (struct vertex
*)node2
;
79 if (v1
!= NULL
&& v2
!= NULL
) {
80 /* network vertices must be chosen before router vertices of
82 * cost in order to find all shortest paths
84 if (((v1
->distance
- v2
->distance
) == 0)
85 && (v1
->type
!= v2
->type
)) {
87 case OSPF_VERTEX_NETWORK
:
89 case OSPF_VERTEX_ROUTER
:
93 return (v1
->distance
- v2
->distance
);
98 static void update_stat(void *node
, int position
)
100 struct vertex
*v
= node
;
102 /* Set the status of the vertex, when its position changes. */
103 *(v
->stat
) = position
;
106 static struct vertex_nexthop
*vertex_nexthop_new(void)
108 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
111 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
113 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
116 /* Free the canonical nexthop objects for an area, ie the nexthop objects
117 * attached to the first-hop router vertices, and any intervening network
120 static void ospf_canonical_nexthops_free(struct vertex
*root
)
122 struct listnode
*node
, *nnode
;
123 struct vertex
*child
;
125 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
126 struct listnode
*n2
, *nn2
;
127 struct vertex_parent
*vp
;
129 /* router vertices through an attached network each
130 * have a distinct (canonical / not inherited) nexthop
131 * which must be freed.
133 * A network vertex can only have router vertices as its
134 * children, so only one level of recursion is possible.
136 if (child
->type
== OSPF_VERTEX_NETWORK
)
137 ospf_canonical_nexthops_free(child
);
139 /* Free child nexthops pointing back to this root vertex */
140 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
))
141 if (vp
->parent
== root
&& vp
->nexthop
) {
142 vertex_nexthop_free(vp
->nexthop
);
148 /* TODO: Parent list should be excised, in favour of maintaining only
149 * vertex_nexthop, with refcounts.
151 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
152 struct vertex_nexthop
*hop
)
154 struct vertex_parent
*new;
156 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
159 new->backlink
= backlink
;
164 static void vertex_parent_free(void *p
)
166 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
169 static struct vertex
*ospf_vertex_new(struct ospf_lsa
*lsa
)
173 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
176 new->stat
= &(lsa
->stat
);
177 new->type
= lsa
->data
->type
;
178 new->id
= lsa
->data
->id
;
179 new->lsa
= lsa
->data
;
180 new->children
= list_new();
181 new->parents
= list_new();
182 new->parents
->del
= vertex_parent_free
;
184 listnode_add(&vertex_list
, new);
186 if (IS_DEBUG_OSPF_EVENT
)
187 zlog_debug("%s: Created %s vertex %s", __func__
,
188 new->type
== OSPF_VERTEX_ROUTER
? "Router"
190 inet_ntoa(new->lsa
->id
));
194 static void ospf_vertex_free(void *data
)
196 struct vertex
*v
= data
;
198 if (IS_DEBUG_OSPF_EVENT
)
199 zlog_debug("%s: Free %s vertex %s", __func__
,
200 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
201 inet_ntoa(v
->lsa
->id
));
203 /* There should be no parents potentially holding references to this
205 * Children however may still be there, but presumably referenced by
209 // assert (listcount (v->parents) == 0);
212 list_delete(&v
->children
);
215 list_delete(&v
->parents
);
219 XFREE(MTYPE_OSPF_VERTEX
, v
);
222 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
223 int print_parents
, int print_children
)
225 if (!IS_DEBUG_OSPF_EVENT
)
228 zlog_debug("%s %s vertex %s distance %u flags %u", msg
,
229 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
230 inet_ntoa(v
->lsa
->id
), v
->distance
, (unsigned int)v
->flags
);
233 struct listnode
*node
;
234 struct vertex_parent
*vp
;
236 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
241 "parent %s backlink %d nexthop %s interface %s",
242 inet_ntoa(vp
->parent
->lsa
->id
),
244 inet_ntop(AF_INET
, &vp
->nexthop
->router
,
247 ? IF_NAME(vp
->nexthop
->oi
)
253 if (print_children
) {
254 struct listnode
*cnode
;
257 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
258 ospf_vertex_dump(" child:", cv
, 0, 0);
263 /* Add a vertex to the list of children in each of its parents. */
264 static void ospf_vertex_add_parent(struct vertex
*v
)
266 struct vertex_parent
*vp
;
267 struct listnode
*node
;
269 assert(v
&& v
->parents
);
271 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
272 assert(vp
->parent
&& vp
->parent
->children
);
274 /* No need to add two links from the same parent. */
275 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
276 listnode_add(vp
->parent
->children
, v
);
280 static void ospf_spf_init(struct ospf_area
*area
)
284 /* Create root node. */
285 v
= ospf_vertex_new(area
->router_lsa_self
);
289 /* Reset ABR and ASBR router counts. */
291 area
->asbr_count
= 0;
294 /* return index of link back to V from W, or -1 if no link found */
295 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
297 unsigned int i
, length
;
298 struct router_lsa
*rl
;
299 struct network_lsa
*nl
;
301 /* In case of W is Network LSA. */
302 if (w
->type
== OSPF_NETWORK_LSA
) {
303 if (v
->type
== OSPF_NETWORK_LSA
)
306 nl
= (struct network_lsa
*)w
;
307 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
309 for (i
= 0; i
< length
; i
++)
310 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
315 /* In case of W is Router LSA. */
316 if (w
->type
== OSPF_ROUTER_LSA
) {
317 rl
= (struct router_lsa
*)w
;
319 length
= ntohs(w
->length
);
321 for (i
= 0; i
< ntohs(rl
->links
)
322 && length
>= sizeof(struct router_lsa
);
324 switch (rl
->link
[i
].type
) {
325 case LSA_LINK_TYPE_POINTOPOINT
:
326 case LSA_LINK_TYPE_VIRTUALLINK
:
328 if (v
->type
== OSPF_ROUTER_LSA
329 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
334 case LSA_LINK_TYPE_TRANSIT
:
335 /* Network LSA ID. */
336 if (v
->type
== OSPF_NETWORK_LSA
337 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
342 case LSA_LINK_TYPE_STUB
:
343 /* Stub can't lead anywhere, carry on */
353 /* Find the next link after prev_link from v to w. If prev_link is
354 * NULL, return the first link from v to w. Ignore stub and virtual links;
355 * these link types will never be returned.
357 static struct router_lsa_link
*
358 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
359 struct router_lsa_link
*prev_link
)
363 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
364 struct router_lsa_link
*l
;
366 if (w
->type
== OSPF_VERTEX_ROUTER
)
367 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
369 if (prev_link
== NULL
)
370 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
372 p
= (uint8_t *)prev_link
;
373 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
374 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
377 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
380 l
= (struct router_lsa_link
*)p
;
382 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
383 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
385 if (l
->m
[0].type
!= lsa_type
)
388 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
395 static void ospf_spf_flush_parents(struct vertex
*w
)
397 struct vertex_parent
*vp
;
398 struct listnode
*ln
, *nn
;
400 /* delete the existing nexthops */
401 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
402 list_delete_node(w
->parents
, ln
);
403 vertex_parent_free(vp
);
408 * Consider supplied next-hop for inclusion to the supplied list of
409 * equal-cost next-hops, adjust list as neccessary.
411 static void ospf_spf_add_parent(struct vertex
*v
, struct vertex
*w
,
412 struct vertex_nexthop
*newhop
,
413 unsigned int distance
)
415 struct vertex_parent
*vp
, *wp
;
416 struct listnode
*node
;
418 /* we must have a newhop, and a distance */
419 assert(v
&& w
&& newhop
);
422 /* IFF w has already been assigned a distance, then we shouldn't get
424 * unless callers have determined V(l)->W is shortest / equal-shortest
425 * path (0 is a special case distance (no distance yet assigned)).
428 assert(distance
<= w
->distance
);
430 w
->distance
= distance
;
432 if (IS_DEBUG_OSPF_EVENT
) {
433 char buf
[2][INET_ADDRSTRLEN
];
435 "%s: Adding %s as parent of %s", __func__
,
436 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
437 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1],
441 /* Adding parent for a new, better path: flush existing parents from W.
443 if (distance
< w
->distance
) {
444 if (IS_DEBUG_OSPF_EVENT
)
446 "%s: distance %d better than %d, flushing existing parents",
447 __func__
, distance
, w
->distance
);
448 ospf_spf_flush_parents(w
);
449 w
->distance
= distance
;
452 /* new parent is <= existing parents, add it to parent list (if nexthop
453 * not on parent list)
455 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
456 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
457 if (IS_DEBUG_OSPF_EVENT
)
459 "%s: ... nexthop already on parent list, skipping add",
465 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
);
466 listnode_add(w
->parents
, vp
);
471 /* 16.1.1. Calculate nexthop from root through V (parent) to
472 * vertex W (destination), with given distance from root->W.
474 * The link must be supplied if V is the root vertex. In all other cases
477 * Note that this function may fail, hence the state of the destination
478 * vertex, W, should /not/ be modified in a dependent manner until
479 * this function returns. This function will update the W vertex with the
480 * provided distance as appropriate.
482 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
483 struct vertex
*v
, struct vertex
*w
,
484 struct router_lsa_link
*l
,
485 unsigned int distance
, int lsa_pos
)
487 struct listnode
*node
, *nnode
;
488 struct vertex_nexthop
*nh
;
489 struct vertex_parent
*vp
;
490 struct ospf_interface
*oi
= NULL
;
491 unsigned int added
= 0;
495 if (IS_DEBUG_OSPF_EVENT
) {
496 zlog_debug("ospf_nexthop_calculation(): Start");
497 ospf_vertex_dump("V (parent):", v
, 1, 1);
498 ospf_vertex_dump("W (dest) :", w
, 1, 1);
499 zlog_debug("V->W distance: %d", distance
);
502 if (v
== area
->spf
) {
503 /* 16.1.1 para 4. In the first case, the parent vertex (V) is
505 root (the calculating router itself). This means that the
506 destination is either a directly connected network or
508 connected router. The outgoing interface in this case is
510 the OSPF interface connecting to the destination
514 /* we *must* be supplied with the link data */
516 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
519 "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
521 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
522 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
527 if (IS_DEBUG_OSPF_EVENT
) {
529 "%s: considering link:%s "
530 "type:%d link_id:%s link_data:%s",
531 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
532 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
533 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
537 if (w
->type
== OSPF_VERTEX_ROUTER
) {
538 /* l is a link from v to w
539 * l2 will be link from w to v
541 struct router_lsa_link
*l2
= NULL
;
543 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
544 struct in_addr nexthop
= {.s_addr
= 0};
546 /* If the destination is a router which connects
548 the calculating router via a
550 network, the destination's next hop IP
552 can be determined by examining the
554 router-LSA: each link pointing back to the
555 calculating router and having a Link Data
557 belonging to the Point-to-MultiPoint network
558 provides an IP address of the next hop
561 At this point l is a link from V to W, and V
563 root ("us"). If it is a point-to-multipoint
565 then look through the links in the opposite
567 If any of them have an address that lands
569 subnet declared by the PtMP link, then that
571 is a constituent of the PtMP link, and its
573 a nexthop address for V.
575 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
) {
576 /* Having nexthop = 0 is tempting, but
578 It breaks AS-External routes with a
581 ospf_ase_complete_direct_routes()
583 assume we've reached the last hop and
585 forwarding address as nexthop.
586 Also, users may configure
587 multi-access links in p2p mode,
588 so we need the IP to ARP the nexthop.
590 struct ospf_neighbor
*nbr_w
;
592 nbr_w
= ospf_nbr_lookup_by_routerid(
593 oi
->nbrs
, &l
->link_id
);
596 nexthop
= nbr_w
->src
;
599 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
600 struct prefix_ipv4 la
;
603 la
.prefixlen
= oi
->address
->prefixlen
;
605 /* V links to W on PtMP interface
606 - find the interface address on W */
607 while ((l2
= ospf_get_next_link(w
, v
,
609 la
.prefix
= l2
->link_data
;
611 if (prefix_cmp((struct prefix
616 /* link_data is on our PtMP
619 nexthop
= l2
->link_data
;
625 /* found all necessary info to build
627 nh
= vertex_nexthop_new();
629 nh
->router
= nexthop
;
630 ospf_spf_add_parent(v
, w
, nh
, distance
);
634 "%s: could not determine nexthop for link %s",
635 __func__
, oi
->ifp
->name
);
636 } /* end point-to-point link from V to W */
637 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
638 struct ospf_vl_data
*vl_data
;
640 /* VLink implementation limitations:
641 * a) vl_data can only reference one nexthop, so
643 * to backbone through VLinks. Though
645 * summaries may be considered, and those can
647 * b) We can only use /one/ VLink, even if
649 * exist this router through multiple
652 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
656 && CHECK_FLAG(vl_data
->flags
,
657 OSPF_VL_FLAG_APPROVED
)) {
658 nh
= vertex_nexthop_new();
659 nh
->oi
= vl_data
->nexthop
.oi
;
660 nh
->router
= vl_data
->nexthop
.router
;
661 ospf_spf_add_parent(v
, w
, nh
, distance
);
665 "ospf_nexthop_calculation(): "
666 "vl_data for VL link not found");
667 } /* end virtual-link from V to W */
669 } /* end W is a Router vertex */
671 assert(w
->type
== OSPF_VERTEX_NETWORK
);
673 nh
= vertex_nexthop_new();
675 nh
->router
.s_addr
= 0; /* Nexthop not required */
676 ospf_spf_add_parent(v
, w
, nh
, distance
);
679 } /* end V is the root */
680 /* Check if W's parent is a network connected to root. */
681 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
682 /* See if any of V's parents are the root. */
683 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
684 if (vp
->parent
== area
->spf
) /* connects to root? */
686 /* 16.1.1 para 5. ...the parent vertex is a
688 * directly connects the calculating router to
690 * router. The list of next hops is then
692 * examining the destination's router-LSA...
695 assert(w
->type
== OSPF_VERTEX_ROUTER
);
696 while ((l
= ospf_get_next_link(w
, v
, l
))) {
697 /* ...For each link in the router-LSA
698 * that points back to the
699 * parent network, the link's Link Data
700 * field provides the IP
701 * address of a next hop router. The
702 * outgoing interface to
703 * use can then be derived from the next
705 * it can be inherited from the parent
708 nh
= vertex_nexthop_new();
709 nh
->oi
= vp
->nexthop
->oi
;
710 nh
->router
= l
->link_data
;
712 ospf_spf_add_parent(v
, w
, nh
, distance
);
714 /* Note lack of return is deliberate. See next
718 /* NB: This code is non-trivial.
720 * E.g. it is not enough to know that V connects to the root. It
722 * also important that the while above, looping through all
724 * W->V found at least one link, so that we know there is
725 * bi-directional connectivity between V and W (which need not
727 * case, e.g. when OSPF has not yet converged fully).
729 * we /always/ return here, without having checked that
731 * actually resulted in a valid nexthop being created, then we
733 * prevent SPF from finding/using higher cost paths.
735 * It is important, if root->V->W has not been added, that we
737 * through to the intervening-router nexthop code below. So as
739 * ensure other paths to V may be used. This avoids unnecessary
740 * blackholes while OSPF is convergening.
742 * I.e. we may have arrived at this function, examining V -> W,
744 * workable paths other than root -> V, and it's important to
746 * getting "confused" by non-working root->V->W path - it's
748 * to *not* lose the working non-root paths, just because of a
749 * non-viable root->V->W.
751 * See also bug #330 (required reading!), and:
753 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
759 /* 16.1.1 para 4. If there is at least one intervening router in the
760 * current shortest path between the destination and the root, the
761 * destination simply inherits the set of next hops from the
764 if (IS_DEBUG_OSPF_EVENT
)
765 zlog_debug("%s: Intervening routers, adding parent(s)",
768 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
770 ospf_spf_add_parent(v
, w
, vp
->nexthop
, distance
);
776 /* RFC2328 Section 16.1 (2).
777 * v is on the SPF tree. Examine the links in v's LSA. Update the list
778 * of candidates with any vertices not already on the list. If a lower-cost
779 * path is found to a vertex already on the candidate list, store the new cost.
781 static void ospf_spf_next(struct vertex
*v
, struct ospf
*ospf
,
782 struct ospf_area
*area
, struct pqueue
*candidate
)
784 struct ospf_lsa
*w_lsa
= NULL
;
787 struct router_lsa_link
*l
= NULL
;
789 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
791 /* If this is a router-LSA, and bit V of the router-LSA (see Section
792 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
793 if (v
->type
== OSPF_VERTEX_ROUTER
) {
794 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
795 area
->transit
= OSPF_TRANSIT_TRUE
;
798 if (IS_DEBUG_OSPF_EVENT
)
799 zlog_debug("%s: Next vertex of %s vertex %s", __func__
,
800 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
801 inet_ntoa(v
->lsa
->id
));
803 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
804 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
808 unsigned int distance
;
810 /* In case of V is Router-LSA. */
811 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
812 l
= (struct router_lsa_link
*)p
;
814 lsa_pos
= lsa_pos_next
; /* LSA link position */
816 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
817 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
819 /* (a) If this is a link to a stub network, examine the
821 link in V's LSA. Links to stub networks will be
822 considered in the second stage of the shortest path
824 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
827 /* (b) Otherwise, W is a transit vertex (router or
829 network). Look up the vertex W's LSA (router-LSA or
830 network-LSA) in Area A's link state database. */
832 case LSA_LINK_TYPE_POINTOPOINT
:
833 case LSA_LINK_TYPE_VIRTUALLINK
:
834 if (type
== LSA_LINK_TYPE_VIRTUALLINK
) {
835 if (IS_DEBUG_OSPF_EVENT
)
837 "looking up LSA through VL: %s",
838 inet_ntoa(l
->link_id
));
841 w_lsa
= ospf_lsa_lookup(ospf
, area
,
843 l
->link_id
, l
->link_id
);
845 if (IS_DEBUG_OSPF_EVENT
)
847 "found Router LSA %s",
848 inet_ntoa(l
->link_id
));
851 case LSA_LINK_TYPE_TRANSIT
:
852 if (IS_DEBUG_OSPF_EVENT
)
854 "Looking up Network LSA, ID: %s",
855 inet_ntoa(l
->link_id
));
856 w_lsa
= ospf_lsa_lookup_by_id(
857 area
, OSPF_NETWORK_LSA
, l
->link_id
);
859 if (IS_DEBUG_OSPF_EVENT
)
860 zlog_debug("found the LSA");
863 flog_warn(EC_OSPF_LSA
,
864 "Invalid LSA link type %d", type
);
868 /* In case of V is Network-LSA. */
869 r
= (struct in_addr
*)p
;
870 p
+= sizeof(struct in_addr
);
872 /* Lookup the vertex W's LSA. */
873 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
876 if (IS_DEBUG_OSPF_EVENT
)
877 zlog_debug("found Router LSA %s",
878 inet_ntoa(w_lsa
->data
->id
));
882 /* (b cont.) If the LSA does not exist, or its LS age is equal
883 to MaxAge, or it does not have a link back to vertex V,
884 examine the next link in V's LSA.[23] */
886 if (IS_DEBUG_OSPF_EVENT
)
887 zlog_debug("No LSA found");
891 if (IS_LSA_MAXAGE(w_lsa
)) {
892 if (IS_DEBUG_OSPF_EVENT
)
893 zlog_debug("LSA is MaxAge");
897 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
898 if (IS_DEBUG_OSPF_EVENT
)
899 zlog_debug("The LSA doesn't have a link back");
903 /* (c) If vertex W is already on the shortest-path tree, examine
904 the next link in the LSA. */
905 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
906 if (IS_DEBUG_OSPF_EVENT
)
907 zlog_debug("The LSA is already in SPF");
911 /* (d) Calculate the link state cost D of the resulting path
912 from the root to vertex W. D is equal to the sum of the link
913 state cost of the (already calculated) shortest path to
914 vertex V and the advertised cost of the link between vertices
917 /* calculate link cost D. */
918 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
919 distance
= v
->distance
+ ntohs(l
->m
[0].metric
);
920 else /* v is not a Router-LSA */
921 distance
= v
->distance
;
923 /* Is there already vertex W in candidate list? */
924 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
925 /* prepare vertex W. */
926 w
= ospf_vertex_new(w_lsa
);
928 /* Calculate nexthop to W. */
929 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
931 pqueue_enqueue(w
, candidate
);
932 else if (IS_DEBUG_OSPF_EVENT
)
933 zlog_debug("Nexthop Calc failed");
934 } else if (w_lsa
->stat
>= 0) {
935 /* Get the vertex from candidates. */
936 w
= candidate
->array
[w_lsa
->stat
];
938 /* if D is greater than. */
939 if (w
->distance
< distance
) {
943 else if (w
->distance
== distance
) {
944 /* Found an equal-cost path to W.
945 * Calculate nexthop of to W from V. */
946 ospf_nexthop_calculation(area
, v
, w
, l
,
951 /* Found a lower-cost path to W.
952 * nexthop_calculation is conditional, if it
954 * valid nexthop it will call spf_add_parents,
956 * will flush the old parents
958 if (ospf_nexthop_calculation(area
, v
, w
, l
,
960 /* Decrease the key of the node in the
962 * trickle-sort it up towards root, just
964 * node should now be the new root due
966 * (next pqueu_{de,en}queue will fully
967 * re-heap the queue).
969 trickle_up(w_lsa
->stat
, candidate
);
971 } /* end W is already on the candidate list */
972 } /* end loop over the links in V's LSA */
975 static void ospf_spf_dump(struct vertex
*v
, int i
)
977 struct listnode
*cnode
;
978 struct listnode
*nnode
;
979 struct vertex_parent
*parent
;
981 if (v
->type
== OSPF_VERTEX_ROUTER
) {
982 if (IS_DEBUG_OSPF_EVENT
)
983 zlog_debug("SPF Result: %d [R] %s", i
,
984 inet_ntoa(v
->lsa
->id
));
986 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
987 if (IS_DEBUG_OSPF_EVENT
)
988 zlog_debug("SPF Result: %d [N] %s/%d", i
,
989 inet_ntoa(v
->lsa
->id
),
990 ip_masklen(lsa
->mask
));
993 if (IS_DEBUG_OSPF_EVENT
)
994 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
995 zlog_debug(" nexthop %p %s %s", (void *)parent
->nexthop
,
996 inet_ntoa(parent
->nexthop
->router
),
998 ? IF_NAME(parent
->nexthop
->oi
)
1004 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1005 ospf_spf_dump(v
, i
);
1008 /* Second stage of SPF calculation. */
1009 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1010 struct route_table
*rt
, int parent_is_root
)
1012 struct listnode
*cnode
, *cnnode
;
1013 struct vertex
*child
;
1015 if (IS_DEBUG_OSPF_EVENT
)
1016 zlog_debug("ospf_process_stub():processing stubs for area %s",
1017 inet_ntoa(area
->area_id
));
1018 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1021 struct router_lsa_link
*l
;
1022 struct router_lsa
*rlsa
;
1025 if (IS_DEBUG_OSPF_EVENT
)
1027 "ospf_process_stubs():processing router LSA, id: %s",
1028 inet_ntoa(v
->lsa
->id
));
1029 rlsa
= (struct router_lsa
*)v
->lsa
;
1032 if (IS_DEBUG_OSPF_EVENT
)
1034 "ospf_process_stubs(): we have %d links to process",
1035 ntohs(rlsa
->links
));
1036 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1037 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1040 l
= (struct router_lsa_link
*)p
;
1042 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1043 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1045 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
1046 ospf_intra_add_stub(rt
, l
, v
, area
,
1047 parent_is_root
, lsa_pos
);
1052 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1055 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1056 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1059 /* the first level of routers connected to the root
1060 * should have 'parent_is_root' set, including those
1061 * connected via a network vertex.
1065 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1068 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1070 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1074 void ospf_rtrs_free(struct route_table
*rtrs
)
1076 struct route_node
*rn
;
1077 struct list
*or_list
;
1078 struct ospf_route
* or ;
1079 struct listnode
*node
, *nnode
;
1081 if (IS_DEBUG_OSPF_EVENT
)
1082 zlog_debug("Route: Router Routing Table free");
1084 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1085 if ((or_list
= rn
->info
) != NULL
) {
1086 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1087 ospf_route_free(or);
1089 list_delete(&or_list
);
1091 /* Unlock the node. */
1093 route_unlock_node(rn
);
1095 route_table_finish(rtrs
);
1100 ospf_rtrs_print (struct route_table
*rtrs
)
1102 struct route_node
*rn
;
1103 struct list
*or_list
;
1104 struct listnode
*ln
;
1105 struct listnode
*pnode
;
1106 struct ospf_route
*or;
1107 struct ospf_path
*path
;
1111 if (IS_DEBUG_OSPF_EVENT
)
1112 zlog_debug ("ospf_rtrs_print() start");
1114 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1115 if ((or_list
= rn
->info
) != NULL
)
1116 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1118 switch (or->path_type
)
1120 case OSPF_PATH_INTRA_AREA
:
1121 if (IS_DEBUG_OSPF_EVENT
)
1122 zlog_debug ("%s [%d] area: %s",
1123 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1124 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1127 case OSPF_PATH_INTER_AREA
:
1128 if (IS_DEBUG_OSPF_EVENT
)
1129 zlog_debug ("%s IA [%d] area: %s",
1130 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1131 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1138 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1140 if (path
->nexthop
.s_addr
== 0)
1142 if (IS_DEBUG_OSPF_EVENT
)
1143 zlog_debug (" directly attached to %s\r\n",
1144 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1148 if (IS_DEBUG_OSPF_EVENT
)
1149 zlog_debug (" via %s, %s\r\n",
1150 inet_ntoa (path
->nexthop
),
1151 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1156 zlog_debug ("ospf_rtrs_print() end");
1160 /* Calculating the shortest-path tree for an area. */
1161 static void ospf_spf_calculate(struct ospf
*ospf
, struct ospf_area
*area
,
1162 struct route_table
*new_table
,
1163 struct route_table
*new_rtrs
)
1165 struct pqueue
*candidate
;
1168 if (IS_DEBUG_OSPF_EVENT
) {
1169 zlog_debug("ospf_spf_calculate: Start");
1170 zlog_debug("ospf_spf_calculate: running Dijkstra for area %s",
1171 inet_ntoa(area
->area_id
));
1174 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1175 return this area's calculation. */
1176 if (!area
->router_lsa_self
) {
1177 if (IS_DEBUG_OSPF_EVENT
)
1179 "ospf_spf_calculate: "
1180 "Skip area %s's calculation due to empty router_lsa_self",
1181 inet_ntoa(area
->area_id
));
1185 /* RFC2328 16.1. (1). */
1186 /* Initialize the algorithm's data structures. */
1188 /* This function scans all the LSA database and set the stat field to
1189 * LSA_SPF_NOT_EXPLORED. */
1190 ospf_lsdb_clean_stat(area
->lsdb
);
1191 /* Create a new heap for the candidates. */
1192 candidate
= pqueue_create();
1193 candidate
->cmp
= cmp
;
1194 candidate
->update
= update_stat
;
1196 /* Initialize the shortest-path tree to only the root (which is the
1197 router doing the calculation). */
1198 ospf_spf_init(area
);
1200 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
1203 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1205 /* Set Area A's TransitCapability to FALSE. */
1206 area
->transit
= OSPF_TRANSIT_FALSE
;
1207 area
->shortcut_capability
= 1;
1210 /* RFC2328 16.1. (2). */
1211 ospf_spf_next(v
, ospf
, area
, candidate
);
1213 /* RFC2328 16.1. (3). */
1214 /* If at this step the candidate list is empty, the shortest-
1215 path tree (of transit vertices) has been completely built and
1216 this stage of the procedure terminates. */
1217 if (candidate
->size
== 0)
1220 /* Otherwise, choose the vertex belonging to the candidate list
1221 that is closest to the root, and add it to the shortest-path
1222 tree (removing it from the candidate list in the
1224 /* Extract from the candidates the node with the lower key. */
1225 v
= (struct vertex
*)pqueue_dequeue(candidate
);
1226 /* Update stat field in vertex. */
1227 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1229 ospf_vertex_add_parent(v
);
1231 /* RFC2328 16.1. (4). */
1232 if (v
->type
== OSPF_VERTEX_ROUTER
)
1233 ospf_intra_add_router(new_rtrs
, v
, area
);
1235 ospf_intra_add_transit(new_table
, v
, area
);
1237 /* RFC2328 16.1. (5). */
1238 /* Iterate the algorithm by returning to Step 2. */
1240 } /* end loop until no more candidate vertices */
1242 if (IS_DEBUG_OSPF_EVENT
) {
1243 ospf_spf_dump(area
->spf
, 0);
1244 ospf_route_table_dump(new_table
);
1247 /* Second stage of SPF calculation procedure's */
1248 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1250 /* Free candidate queue. */
1251 pqueue_delete(candidate
);
1253 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1254 /* Free nexthop information, canonical versions of which are attached
1255 * the first level of router vertices attached to the root vertex, see
1256 * ospf_nexthop_calculation.
1258 ospf_canonical_nexthops_free(area
->spf
);
1260 /* Increment SPF Calculation Counter. */
1261 area
->spf_calculation
++;
1263 monotime(&area
->ospf
->ts_spf
);
1264 area
->ts_spf
= area
->ospf
->ts_spf
;
1266 if (IS_DEBUG_OSPF_EVENT
)
1267 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1268 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1270 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1273 list_delete_all_node(&vertex_list
);
1276 /* Timer for SPF calculation. */
1277 static int ospf_spf_calculate_timer(struct thread
*thread
)
1279 struct ospf
*ospf
= THREAD_ARG(thread
);
1280 struct route_table
*new_table
, *new_rtrs
;
1281 struct ospf_area
*area
;
1282 struct listnode
*node
, *nnode
;
1283 struct timeval start_time
, spf_start_time
;
1284 int areas_processed
= 0;
1285 unsigned long ia_time
, prune_time
, rt_time
;
1286 unsigned long abr_time
, total_spf_time
, spf_time
;
1287 char rbuf
[32]; /* reason_buf */
1289 if (IS_DEBUG_OSPF_EVENT
)
1290 zlog_debug("SPF: Timer (SPF calculation expire)");
1292 ospf
->t_spf_calc
= NULL
;
1294 monotime(&spf_start_time
);
1295 /* Allocate new table tree. */
1296 new_table
= route_table_init();
1297 new_rtrs
= route_table_init();
1299 ospf_vl_unapprove(ospf
);
1301 /* Calculate SPF for each area. */
1302 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1303 /* Do backbone last, so as to first discover intra-area paths
1304 * for any back-bone virtual-links
1306 if (ospf
->backbone
&& ospf
->backbone
== area
)
1309 ospf_spf_calculate(ospf
, area
, new_table
, new_rtrs
);
1313 /* SPF for backbone, if required */
1314 if (ospf
->backbone
) {
1315 ospf_spf_calculate(ospf
, ospf
->backbone
, new_table
, new_rtrs
);
1319 spf_time
= monotime_since(&spf_start_time
, NULL
);
1321 ospf_vl_shut_unapproved(ospf
);
1323 monotime(&start_time
);
1324 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1325 ia_time
= monotime_since(&start_time
, NULL
);
1327 monotime(&start_time
);
1328 ospf_prune_unreachable_networks(new_table
);
1329 ospf_prune_unreachable_routers(new_rtrs
);
1330 prune_time
= monotime_since(&start_time
, NULL
);
1332 /* AS-external-LSA calculation should not be performed here. */
1334 /* If new Router Route is installed,
1335 then schedule re-calculate External routes. */
1337 ospf_ase_calculate_schedule(ospf
);
1339 ospf_ase_calculate_timer_add(ospf
);
1341 if (IS_DEBUG_OSPF_EVENT
)
1343 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1344 __PRETTY_FUNCTION__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1345 ospf
->vrf_id
, new_table
->count
);
1346 /* Update routing table. */
1347 monotime(&start_time
);
1348 ospf_route_install(ospf
, new_table
);
1349 rt_time
= monotime_since(&start_time
, NULL
);
1351 /* Update ABR/ASBR routing table */
1352 if (ospf
->old_rtrs
) {
1353 /* old_rtrs's node holds linked list of ospf_route. --kunihiro.
1355 /* ospf_route_delete (ospf->old_rtrs); */
1356 ospf_rtrs_free(ospf
->old_rtrs
);
1359 ospf
->old_rtrs
= ospf
->new_rtrs
;
1360 ospf
->new_rtrs
= new_rtrs
;
1362 monotime(&start_time
);
1363 if (IS_OSPF_ABR(ospf
))
1364 ospf_abr_task(ospf
);
1365 abr_time
= monotime_since(&start_time
, NULL
);
1367 /* Schedule Segment Routing update */
1368 ospf_sr_update_timer_add(ospf
);
1371 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1374 if (spf_reason_flags
) {
1375 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1376 strncat(rbuf
, "R, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1377 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1378 strncat(rbuf
, "N, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1379 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1380 strncat(rbuf
, "S, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1381 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1382 strncat(rbuf
, "AS, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1383 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1384 strncat(rbuf
, "ABR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1385 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1386 strncat(rbuf
, "ASBR, ",
1387 sizeof(rbuf
) - strlen(rbuf
) - 1);
1388 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1389 strncat(rbuf
, "M, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1391 size_t rbuflen
= strlen(rbuf
);
1393 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1398 if (IS_DEBUG_OSPF_EVENT
) {
1399 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1400 zlog_info("\t SPF Time: %ld", spf_time
);
1401 zlog_info("\t InterArea: %ld", ia_time
);
1402 zlog_info("\t Prune: %ld", prune_time
);
1403 zlog_info("\tRouteInstall: %ld", rt_time
);
1404 if (IS_OSPF_ABR(ospf
))
1405 zlog_info("\t ABR: %ld (%d areas)", abr_time
,
1407 zlog_info("Reason(s) for SPF: %s", rbuf
);
1410 ospf_clear_spf_reason_flags();
1415 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1416 set timer for SPF calc. */
1417 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1419 unsigned long delay
, elapsed
, ht
;
1421 if (IS_DEBUG_OSPF_EVENT
)
1422 zlog_debug("SPF: calculation timer scheduled");
1424 /* OSPF instance does not exist. */
1428 ospf_spf_set_reason(reason
);
1430 /* SPF calculation timer is already scheduled. */
1431 if (ospf
->t_spf_calc
) {
1432 if (IS_DEBUG_OSPF_EVENT
)
1434 "SPF: calculation timer is already scheduled: %p",
1435 (void *)ospf
->t_spf_calc
);
1439 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
1441 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1443 if (ht
> ospf
->spf_max_holdtime
)
1444 ht
= ospf
->spf_max_holdtime
;
1446 /* Get SPF calculation delay time. */
1448 /* Got an event within the hold time of last SPF. We need to
1449 * increase the hold_multiplier, if it's not already at/past
1450 * maximum value, and wasn't already increased..
1452 if (ht
< ospf
->spf_max_holdtime
)
1453 ospf
->spf_hold_multiplier
++;
1455 /* always honour the SPF initial delay */
1456 if ((ht
- elapsed
) < ospf
->spf_delay
)
1457 delay
= ospf
->spf_delay
;
1459 delay
= ht
- elapsed
;
1461 /* Event is past required hold-time of last SPF */
1462 delay
= ospf
->spf_delay
;
1463 ospf
->spf_hold_multiplier
= 1;
1466 if (IS_DEBUG_OSPF_EVENT
)
1467 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
1469 ospf
->t_spf_calc
= NULL
;
1470 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,