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"
51 /* Variables to ensure a SPF scheduled log message is printed only once */
53 static unsigned int spf_reason_flags
= 0;
55 static void ospf_clear_spf_reason_flags(void)
60 static void ospf_spf_set_reason(ospf_spf_reason_t reason
)
62 spf_reason_flags
|= 1 << reason
;
65 static void ospf_vertex_free(void *);
66 /* List of allocated vertices, to simplify cleanup of SPF.
67 * Not thread-safe obviously. If it ever needs to be, it'd have to be
68 * dynamically allocated at begin of ospf_spf_calculate
70 static struct list vertex_list
= {.del
= ospf_vertex_free
};
72 /* Heap related functions, for the managment of the candidates, to
73 * be used with pqueue. */
74 static int cmp(void *node1
, void *node2
)
76 struct vertex
*v1
= (struct vertex
*)node1
;
77 struct vertex
*v2
= (struct vertex
*)node2
;
78 if (v1
!= NULL
&& v2
!= NULL
) {
79 /* network vertices must be chosen before router vertices of
81 * cost in order to find all shortest paths
83 if (((v1
->distance
- v2
->distance
) == 0)
84 && (v1
->type
!= v2
->type
)) {
86 case OSPF_VERTEX_NETWORK
:
88 case OSPF_VERTEX_ROUTER
:
92 return (v1
->distance
- v2
->distance
);
97 static void update_stat(void *node
, int position
)
99 struct vertex
*v
= node
;
101 /* Set the status of the vertex, when its position changes. */
102 *(v
->stat
) = position
;
105 static struct vertex_nexthop
*vertex_nexthop_new(void)
107 return XCALLOC(MTYPE_OSPF_NEXTHOP
, sizeof(struct vertex_nexthop
));
110 static void vertex_nexthop_free(struct vertex_nexthop
*nh
)
112 XFREE(MTYPE_OSPF_NEXTHOP
, nh
);
115 /* Free the canonical nexthop objects for an area, ie the nexthop objects
116 * attached to the first-hop router vertices, and any intervening network
119 static void ospf_canonical_nexthops_free(struct vertex
*root
)
121 struct listnode
*node
, *nnode
;
122 struct vertex
*child
;
124 for (ALL_LIST_ELEMENTS(root
->children
, node
, nnode
, child
)) {
125 struct listnode
*n2
, *nn2
;
126 struct vertex_parent
*vp
;
128 /* router vertices through an attached network each
129 * have a distinct (canonical / not inherited) nexthop
130 * which must be freed.
132 * A network vertex can only have router vertices as its
133 * children, so only one level of recursion is possible.
135 if (child
->type
== OSPF_VERTEX_NETWORK
)
136 ospf_canonical_nexthops_free(child
);
138 /* Free child nexthops pointing back to this root vertex */
139 for (ALL_LIST_ELEMENTS(child
->parents
, n2
, nn2
, vp
))
140 if (vp
->parent
== root
&& vp
->nexthop
) {
141 vertex_nexthop_free(vp
->nexthop
);
147 /* TODO: Parent list should be excised, in favour of maintaining only
148 * vertex_nexthop, with refcounts.
150 static struct vertex_parent
*vertex_parent_new(struct vertex
*v
, int backlink
,
151 struct vertex_nexthop
*hop
)
153 struct vertex_parent
*new;
155 new = XMALLOC(MTYPE_OSPF_VERTEX_PARENT
, sizeof(struct vertex_parent
));
158 new->backlink
= backlink
;
163 static void vertex_parent_free(void *p
)
165 XFREE(MTYPE_OSPF_VERTEX_PARENT
, p
);
168 static struct vertex
*ospf_vertex_new(struct ospf_lsa
*lsa
)
172 new = XCALLOC(MTYPE_OSPF_VERTEX
, sizeof(struct vertex
));
175 new->stat
= &(lsa
->stat
);
176 new->type
= lsa
->data
->type
;
177 new->id
= lsa
->data
->id
;
178 new->lsa
= lsa
->data
;
179 new->children
= list_new();
180 new->parents
= list_new();
181 new->parents
->del
= vertex_parent_free
;
183 listnode_add(&vertex_list
, new);
185 if (IS_DEBUG_OSPF_EVENT
)
186 zlog_debug("%s: Created %s vertex %s", __func__
,
187 new->type
== OSPF_VERTEX_ROUTER
? "Router"
189 inet_ntoa(new->lsa
->id
));
193 static void ospf_vertex_free(void *data
)
195 struct vertex
*v
= data
;
197 if (IS_DEBUG_OSPF_EVENT
)
198 zlog_debug("%s: Free %s vertex %s", __func__
,
199 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
200 inet_ntoa(v
->lsa
->id
));
202 /* There should be no parents potentially holding references to this
204 * Children however may still be there, but presumably referenced by
208 // assert (listcount (v->parents) == 0);
211 list_delete_and_null(&v
->children
);
214 list_delete_and_null(&v
->parents
);
218 XFREE(MTYPE_OSPF_VERTEX
, v
);
221 static void ospf_vertex_dump(const char *msg
, struct vertex
*v
,
222 int print_parents
, int print_children
)
224 if (!IS_DEBUG_OSPF_EVENT
)
227 zlog_debug("%s %s vertex %s distance %u flags %u", msg
,
228 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
229 inet_ntoa(v
->lsa
->id
), v
->distance
, (unsigned int)v
->flags
);
232 struct listnode
*node
;
233 struct vertex_parent
*vp
;
235 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
240 "parent %s backlink %d nexthop %s interface %s",
241 inet_ntoa(vp
->parent
->lsa
->id
),
243 inet_ntop(AF_INET
, &vp
->nexthop
->router
,
246 ? IF_NAME(vp
->nexthop
->oi
)
252 if (print_children
) {
253 struct listnode
*cnode
;
256 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, cv
))
257 ospf_vertex_dump(" child:", cv
, 0, 0);
262 /* Add a vertex to the list of children in each of its parents. */
263 static void ospf_vertex_add_parent(struct vertex
*v
)
265 struct vertex_parent
*vp
;
266 struct listnode
*node
;
268 assert(v
&& v
->parents
);
270 for (ALL_LIST_ELEMENTS_RO(v
->parents
, node
, vp
)) {
271 assert(vp
->parent
&& vp
->parent
->children
);
273 /* No need to add two links from the same parent. */
274 if (listnode_lookup(vp
->parent
->children
, v
) == NULL
)
275 listnode_add(vp
->parent
->children
, v
);
279 static void ospf_spf_init(struct ospf_area
*area
)
283 /* Create root node. */
284 v
= ospf_vertex_new(area
->router_lsa_self
);
288 /* Reset ABR and ASBR router counts. */
290 area
->asbr_count
= 0;
293 /* return index of link back to V from W, or -1 if no link found */
294 static int ospf_lsa_has_link(struct lsa_header
*w
, struct lsa_header
*v
)
296 unsigned int i
, length
;
297 struct router_lsa
*rl
;
298 struct network_lsa
*nl
;
300 /* In case of W is Network LSA. */
301 if (w
->type
== OSPF_NETWORK_LSA
) {
302 if (v
->type
== OSPF_NETWORK_LSA
)
305 nl
= (struct network_lsa
*)w
;
306 length
= (ntohs(w
->length
) - OSPF_LSA_HEADER_SIZE
- 4) / 4;
308 for (i
= 0; i
< length
; i
++)
309 if (IPV4_ADDR_SAME(&nl
->routers
[i
], &v
->id
))
314 /* In case of W is Router LSA. */
315 if (w
->type
== OSPF_ROUTER_LSA
) {
316 rl
= (struct router_lsa
*)w
;
318 length
= ntohs(w
->length
);
320 for (i
= 0; i
< ntohs(rl
->links
)
321 && length
>= sizeof(struct router_lsa
);
323 switch (rl
->link
[i
].type
) {
324 case LSA_LINK_TYPE_POINTOPOINT
:
325 case LSA_LINK_TYPE_VIRTUALLINK
:
327 if (v
->type
== OSPF_ROUTER_LSA
328 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
333 case LSA_LINK_TYPE_TRANSIT
:
334 /* Network LSA ID. */
335 if (v
->type
== OSPF_NETWORK_LSA
336 && IPV4_ADDR_SAME(&rl
->link
[i
].link_id
,
341 case LSA_LINK_TYPE_STUB
:
342 /* Stub can't lead anywhere, carry on */
352 /* Find the next link after prev_link from v to w. If prev_link is
353 * NULL, return the first link from v to w. Ignore stub and virtual links;
354 * these link types will never be returned.
356 static struct router_lsa_link
*
357 ospf_get_next_link(struct vertex
*v
, struct vertex
*w
,
358 struct router_lsa_link
*prev_link
)
362 uint8_t lsa_type
= LSA_LINK_TYPE_TRANSIT
;
363 struct router_lsa_link
*l
;
365 if (w
->type
== OSPF_VERTEX_ROUTER
)
366 lsa_type
= LSA_LINK_TYPE_POINTOPOINT
;
368 if (prev_link
== NULL
)
369 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
371 p
= (uint8_t *)prev_link
;
372 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
373 + (prev_link
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
376 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
379 l
= (struct router_lsa_link
*)p
;
381 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
382 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
384 if (l
->m
[0].type
!= lsa_type
)
387 if (IPV4_ADDR_SAME(&l
->link_id
, &w
->id
))
394 static void ospf_spf_flush_parents(struct vertex
*w
)
396 struct vertex_parent
*vp
;
397 struct listnode
*ln
, *nn
;
399 /* delete the existing nexthops */
400 for (ALL_LIST_ELEMENTS(w
->parents
, ln
, nn
, vp
)) {
401 list_delete_node(w
->parents
, ln
);
402 vertex_parent_free(vp
);
407 * Consider supplied next-hop for inclusion to the supplied list of
408 * equal-cost next-hops, adjust list as neccessary.
410 static void ospf_spf_add_parent(struct vertex
*v
, struct vertex
*w
,
411 struct vertex_nexthop
*newhop
,
412 unsigned int distance
)
414 struct vertex_parent
*vp
, *wp
;
415 struct listnode
*node
;
417 /* we must have a newhop, and a distance */
418 assert(v
&& w
&& newhop
);
421 /* IFF w has already been assigned a distance, then we shouldn't get
423 * unless callers have determined V(l)->W is shortest / equal-shortest
424 * path (0 is a special case distance (no distance yet assigned)).
427 assert(distance
<= w
->distance
);
429 w
->distance
= distance
;
431 if (IS_DEBUG_OSPF_EVENT
) {
432 char buf
[2][INET_ADDRSTRLEN
];
434 "%s: Adding %s as parent of %s", __func__
,
435 inet_ntop(AF_INET
, &v
->lsa
->id
, buf
[0], sizeof(buf
[0])),
436 inet_ntop(AF_INET
, &w
->lsa
->id
, buf
[1],
440 /* Adding parent for a new, better path: flush existing parents from W.
442 if (distance
< w
->distance
) {
443 if (IS_DEBUG_OSPF_EVENT
)
445 "%s: distance %d better than %d, flushing existing parents",
446 __func__
, distance
, w
->distance
);
447 ospf_spf_flush_parents(w
);
448 w
->distance
= distance
;
451 /* new parent is <= existing parents, add it to parent list (if nexthop
452 * not on parent list)
454 for (ALL_LIST_ELEMENTS_RO(w
->parents
, node
, wp
)) {
455 if (memcmp(newhop
, wp
->nexthop
, sizeof(*newhop
)) == 0) {
456 if (IS_DEBUG_OSPF_EVENT
)
458 "%s: ... nexthop already on parent list, skipping add",
464 vp
= vertex_parent_new(v
, ospf_lsa_has_link(w
->lsa
, v
->lsa
), newhop
);
465 listnode_add(w
->parents
, vp
);
470 /* 16.1.1. Calculate nexthop from root through V (parent) to
471 * vertex W (destination), with given distance from root->W.
473 * The link must be supplied if V is the root vertex. In all other cases
476 * Note that this function may fail, hence the state of the destination
477 * vertex, W, should /not/ be modified in a dependent manner until
478 * this function returns. This function will update the W vertex with the
479 * provided distance as appropriate.
481 static unsigned int ospf_nexthop_calculation(struct ospf_area
*area
,
482 struct vertex
*v
, struct vertex
*w
,
483 struct router_lsa_link
*l
,
484 unsigned int distance
, int lsa_pos
)
486 struct listnode
*node
, *nnode
;
487 struct vertex_nexthop
*nh
;
488 struct vertex_parent
*vp
;
489 struct ospf_interface
*oi
= NULL
;
490 unsigned int added
= 0;
494 if (IS_DEBUG_OSPF_EVENT
) {
495 zlog_debug("ospf_nexthop_calculation(): Start");
496 ospf_vertex_dump("V (parent):", v
, 1, 1);
497 ospf_vertex_dump("W (dest) :", w
, 1, 1);
498 zlog_debug("V->W distance: %d", distance
);
501 if (v
== area
->spf
) {
502 /* 16.1.1 para 4. In the first case, the parent vertex (V) is
504 root (the calculating router itself). This means that the
505 destination is either a directly connected network or
507 connected router. The outgoing interface in this case is
509 the OSPF interface connecting to the destination
513 /* we *must* be supplied with the link data */
515 oi
= ospf_if_lookup_by_lsa_pos(area
, lsa_pos
);
518 "%s: OI not found in LSA: lsa_pos:%d link_id:%s link_data:%s",
520 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
521 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
526 if (IS_DEBUG_OSPF_EVENT
) {
528 "%s: considering link:%s "
529 "type:%d link_id:%s link_data:%s",
530 __func__
, oi
->ifp
->name
, l
->m
[0].type
,
531 inet_ntop(AF_INET
, &l
->link_id
, buf1
, BUFSIZ
),
532 inet_ntop(AF_INET
, &l
->link_data
, buf2
,
536 if (w
->type
== OSPF_VERTEX_ROUTER
) {
537 /* l is a link from v to w
538 * l2 will be link from w to v
540 struct router_lsa_link
*l2
= NULL
;
542 if (l
->m
[0].type
== LSA_LINK_TYPE_POINTOPOINT
) {
543 struct in_addr nexthop
= {.s_addr
= 0};
545 /* If the destination is a router which connects
547 the calculating router via a
549 network, the destination's next hop IP
551 can be determined by examining the
553 router-LSA: each link pointing back to the
554 calculating router and having a Link Data
556 belonging to the Point-to-MultiPoint network
557 provides an IP address of the next hop
560 At this point l is a link from V to W, and V
562 root ("us"). If it is a point-to-multipoint
564 then look through the links in the opposite
566 If any of them have an address that lands
568 subnet declared by the PtMP link, then that
570 is a constituent of the PtMP link, and its
572 a nexthop address for V.
574 if (oi
->type
== OSPF_IFTYPE_POINTOPOINT
) {
575 /* Having nexthop = 0 is tempting, but
577 It breaks AS-External routes with a
580 ospf_ase_complete_direct_routes()
582 assume we've reached the last hop and
584 forwarding address as nexthop.
585 Also, users may configure
586 multi-access links in p2p mode,
587 so we need the IP to ARP the nexthop.
589 struct ospf_neighbor
*nbr_w
;
591 nbr_w
= ospf_nbr_lookup_by_routerid(
592 oi
->nbrs
, &l
->link_id
);
595 nexthop
= nbr_w
->src
;
598 == OSPF_IFTYPE_POINTOMULTIPOINT
) {
599 struct prefix_ipv4 la
;
602 la
.prefixlen
= oi
->address
->prefixlen
;
604 /* V links to W on PtMP interface
605 - find the interface address on W */
606 while ((l2
= ospf_get_next_link(w
, v
,
608 la
.prefix
= l2
->link_data
;
610 if (prefix_cmp((struct prefix
615 /* link_data is on our PtMP
618 nexthop
= l2
->link_data
;
624 /* found all necessary info to build
626 nh
= vertex_nexthop_new();
628 nh
->router
= nexthop
;
629 ospf_spf_add_parent(v
, w
, nh
, distance
);
633 "%s: could not determine nexthop for link %s",
634 __func__
, oi
->ifp
->name
);
635 } /* end point-to-point link from V to W */
636 else if (l
->m
[0].type
== LSA_LINK_TYPE_VIRTUALLINK
) {
637 struct ospf_vl_data
*vl_data
;
639 /* VLink implementation limitations:
640 * a) vl_data can only reference one nexthop, so
642 * to backbone through VLinks. Though
644 * summaries may be considered, and those can
646 * b) We can only use /one/ VLink, even if
648 * exist this router through multiple
651 vl_data
= ospf_vl_lookup(area
->ospf
, NULL
,
655 && CHECK_FLAG(vl_data
->flags
,
656 OSPF_VL_FLAG_APPROVED
)) {
657 nh
= vertex_nexthop_new();
658 nh
->oi
= vl_data
->nexthop
.oi
;
659 nh
->router
= vl_data
->nexthop
.router
;
660 ospf_spf_add_parent(v
, w
, nh
, distance
);
664 "ospf_nexthop_calculation(): "
665 "vl_data for VL link not found");
666 } /* end virtual-link from V to W */
668 } /* end W is a Router vertex */
670 assert(w
->type
== OSPF_VERTEX_NETWORK
);
672 nh
= vertex_nexthop_new();
674 nh
->router
.s_addr
= 0; /* Nexthop not required */
675 ospf_spf_add_parent(v
, w
, nh
, distance
);
678 } /* end V is the root */
679 /* Check if W's parent is a network connected to root. */
680 else if (v
->type
== OSPF_VERTEX_NETWORK
) {
681 /* See if any of V's parents are the root. */
682 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
683 if (vp
->parent
== area
->spf
) /* connects to root? */
685 /* 16.1.1 para 5. ...the parent vertex is a
687 * directly connects the calculating router to
689 * router. The list of next hops is then
691 * examining the destination's router-LSA...
694 assert(w
->type
== OSPF_VERTEX_ROUTER
);
695 while ((l
= ospf_get_next_link(w
, v
, l
))) {
696 /* ...For each link in the router-LSA
697 * that points back to the
698 * parent network, the link's Link Data
699 * field provides the IP
700 * address of a next hop router. The
701 * outgoing interface to
702 * use can then be derived from the next
704 * it can be inherited from the parent
707 nh
= vertex_nexthop_new();
708 nh
->oi
= vp
->nexthop
->oi
;
709 nh
->router
= l
->link_data
;
711 ospf_spf_add_parent(v
, w
, nh
, distance
);
713 /* Note lack of return is deliberate. See next
717 /* NB: This code is non-trivial.
719 * E.g. it is not enough to know that V connects to the root. It
721 * also important that the while above, looping through all
723 * W->V found at least one link, so that we know there is
724 * bi-directional connectivity between V and W (which need not
726 * case, e.g. when OSPF has not yet converged fully).
728 * we /always/ return here, without having checked that
730 * actually resulted in a valid nexthop being created, then we
732 * prevent SPF from finding/using higher cost paths.
734 * It is important, if root->V->W has not been added, that we
736 * through to the intervening-router nexthop code below. So as
738 * ensure other paths to V may be used. This avoids unnecessary
739 * blackholes while OSPF is convergening.
741 * I.e. we may have arrived at this function, examining V -> W,
743 * workable paths other than root -> V, and it's important to
745 * getting "confused" by non-working root->V->W path - it's
747 * to *not* lose the working non-root paths, just because of a
748 * non-viable root->V->W.
750 * See also bug #330 (required reading!), and:
752 * http://blogs.oracle.com/paulj/entry/the_difference_a_line_makes
758 /* 16.1.1 para 4. If there is at least one intervening router in the
759 * current shortest path between the destination and the root, the
760 * destination simply inherits the set of next hops from the
763 if (IS_DEBUG_OSPF_EVENT
)
764 zlog_debug("%s: Intervening routers, adding parent(s)",
767 for (ALL_LIST_ELEMENTS(v
->parents
, node
, nnode
, vp
)) {
769 ospf_spf_add_parent(v
, w
, vp
->nexthop
, distance
);
775 /* RFC2328 Section 16.1 (2).
776 * v is on the SPF tree. Examine the links in v's LSA. Update the list
777 * of candidates with any vertices not already on the list. If a lower-cost
778 * path is found to a vertex already on the candidate list, store the new cost.
780 static void ospf_spf_next(struct vertex
*v
, struct ospf
*ospf
,
781 struct ospf_area
*area
, struct pqueue
*candidate
)
783 struct ospf_lsa
*w_lsa
= NULL
;
786 struct router_lsa_link
*l
= NULL
;
788 int type
= 0, lsa_pos
= -1, lsa_pos_next
= 0;
790 /* If this is a router-LSA, and bit V of the router-LSA (see Section
791 A.4.2:RFC2328) is set, set Area A's TransitCapability to TRUE. */
792 if (v
->type
== OSPF_VERTEX_ROUTER
) {
793 if (IS_ROUTER_LSA_VIRTUAL((struct router_lsa
*)v
->lsa
))
794 area
->transit
= OSPF_TRANSIT_TRUE
;
797 if (IS_DEBUG_OSPF_EVENT
)
798 zlog_debug("%s: Next vertex of %s vertex %s", __func__
,
799 v
->type
== OSPF_VERTEX_ROUTER
? "Router" : "Network",
800 inet_ntoa(v
->lsa
->id
));
802 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
803 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
807 unsigned int distance
;
809 /* In case of V is Router-LSA. */
810 if (v
->lsa
->type
== OSPF_ROUTER_LSA
) {
811 l
= (struct router_lsa_link
*)p
;
813 lsa_pos
= lsa_pos_next
; /* LSA link position */
815 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
816 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
818 /* (a) If this is a link to a stub network, examine the
820 link in V's LSA. Links to stub networks will be
821 considered in the second stage of the shortest path
823 if ((type
= l
->m
[0].type
) == LSA_LINK_TYPE_STUB
)
826 /* (b) Otherwise, W is a transit vertex (router or
828 network). Look up the vertex W's LSA (router-LSA or
829 network-LSA) in Area A's link state database. */
831 case LSA_LINK_TYPE_POINTOPOINT
:
832 case LSA_LINK_TYPE_VIRTUALLINK
:
833 if (type
== LSA_LINK_TYPE_VIRTUALLINK
) {
834 if (IS_DEBUG_OSPF_EVENT
)
836 "looking up LSA through VL: %s",
837 inet_ntoa(l
->link_id
));
840 w_lsa
= ospf_lsa_lookup(ospf
, area
,
842 l
->link_id
, l
->link_id
);
844 if (IS_DEBUG_OSPF_EVENT
)
846 "found Router LSA %s",
847 inet_ntoa(l
->link_id
));
850 case LSA_LINK_TYPE_TRANSIT
:
851 if (IS_DEBUG_OSPF_EVENT
)
853 "Looking up Network LSA, ID: %s",
854 inet_ntoa(l
->link_id
));
855 w_lsa
= ospf_lsa_lookup_by_id(
856 area
, OSPF_NETWORK_LSA
, l
->link_id
);
858 if (IS_DEBUG_OSPF_EVENT
)
859 zlog_debug("found the LSA");
862 zlog_warn("Invalid LSA link type %d", type
);
866 /* In case of V is Network-LSA. */
867 r
= (struct in_addr
*)p
;
868 p
+= sizeof(struct in_addr
);
870 /* Lookup the vertex W's LSA. */
871 w_lsa
= ospf_lsa_lookup_by_id(area
, OSPF_ROUTER_LSA
,
874 if (IS_DEBUG_OSPF_EVENT
)
875 zlog_debug("found Router LSA %s",
876 inet_ntoa(w_lsa
->data
->id
));
880 /* (b cont.) If the LSA does not exist, or its LS age is equal
881 to MaxAge, or it does not have a link back to vertex V,
882 examine the next link in V's LSA.[23] */
884 if (IS_DEBUG_OSPF_EVENT
)
885 zlog_debug("No LSA found");
889 if (IS_LSA_MAXAGE(w_lsa
)) {
890 if (IS_DEBUG_OSPF_EVENT
)
891 zlog_debug("LSA is MaxAge");
895 if (ospf_lsa_has_link(w_lsa
->data
, v
->lsa
) < 0) {
896 if (IS_DEBUG_OSPF_EVENT
)
897 zlog_debug("The LSA doesn't have a link back");
901 /* (c) If vertex W is already on the shortest-path tree, examine
902 the next link in the LSA. */
903 if (w_lsa
->stat
== LSA_SPF_IN_SPFTREE
) {
904 if (IS_DEBUG_OSPF_EVENT
)
905 zlog_debug("The LSA is already in SPF");
909 /* (d) Calculate the link state cost D of the resulting path
910 from the root to vertex W. D is equal to the sum of the link
911 state cost of the (already calculated) shortest path to
912 vertex V and the advertised cost of the link between vertices
915 /* calculate link cost D. */
916 if (v
->lsa
->type
== OSPF_ROUTER_LSA
)
917 distance
= v
->distance
+ ntohs(l
->m
[0].metric
);
918 else /* v is not a Router-LSA */
919 distance
= v
->distance
;
921 /* Is there already vertex W in candidate list? */
922 if (w_lsa
->stat
== LSA_SPF_NOT_EXPLORED
) {
923 /* prepare vertex W. */
924 w
= ospf_vertex_new(w_lsa
);
926 /* Calculate nexthop to W. */
927 if (ospf_nexthop_calculation(area
, v
, w
, l
, distance
,
929 pqueue_enqueue(w
, candidate
);
930 else if (IS_DEBUG_OSPF_EVENT
)
931 zlog_debug("Nexthop Calc failed");
932 } else if (w_lsa
->stat
>= 0) {
933 /* Get the vertex from candidates. */
934 w
= candidate
->array
[w_lsa
->stat
];
936 /* if D is greater than. */
937 if (w
->distance
< distance
) {
941 else if (w
->distance
== distance
) {
942 /* Found an equal-cost path to W.
943 * Calculate nexthop of to W from V. */
944 ospf_nexthop_calculation(area
, v
, w
, l
,
949 /* Found a lower-cost path to W.
950 * nexthop_calculation is conditional, if it
952 * valid nexthop it will call spf_add_parents,
954 * will flush the old parents
956 if (ospf_nexthop_calculation(area
, v
, w
, l
,
958 /* Decrease the key of the node in the
960 * trickle-sort it up towards root, just
962 * node should now be the new root due
964 * (next pqueu_{de,en}queue will fully
965 * re-heap the queue).
967 trickle_up(w_lsa
->stat
, candidate
);
969 } /* end W is already on the candidate list */
970 } /* end loop over the links in V's LSA */
973 static void ospf_spf_dump(struct vertex
*v
, int i
)
975 struct listnode
*cnode
;
976 struct listnode
*nnode
;
977 struct vertex_parent
*parent
;
979 if (v
->type
== OSPF_VERTEX_ROUTER
) {
980 if (IS_DEBUG_OSPF_EVENT
)
981 zlog_debug("SPF Result: %d [R] %s", i
,
982 inet_ntoa(v
->lsa
->id
));
984 struct network_lsa
*lsa
= (struct network_lsa
*)v
->lsa
;
985 if (IS_DEBUG_OSPF_EVENT
)
986 zlog_debug("SPF Result: %d [N] %s/%d", i
,
987 inet_ntoa(v
->lsa
->id
),
988 ip_masklen(lsa
->mask
));
991 if (IS_DEBUG_OSPF_EVENT
)
992 for (ALL_LIST_ELEMENTS_RO(v
->parents
, nnode
, parent
)) {
993 zlog_debug(" nexthop %p %s %s", (void *)parent
->nexthop
,
994 inet_ntoa(parent
->nexthop
->router
),
996 ? IF_NAME(parent
->nexthop
->oi
)
1002 for (ALL_LIST_ELEMENTS_RO(v
->children
, cnode
, v
))
1003 ospf_spf_dump(v
, i
);
1006 /* Second stage of SPF calculation. */
1007 static void ospf_spf_process_stubs(struct ospf_area
*area
, struct vertex
*v
,
1008 struct route_table
*rt
, int parent_is_root
)
1010 struct listnode
*cnode
, *cnnode
;
1011 struct vertex
*child
;
1013 if (IS_DEBUG_OSPF_EVENT
)
1014 zlog_debug("ospf_process_stub():processing stubs for area %s",
1015 inet_ntoa(area
->area_id
));
1016 if (v
->type
== OSPF_VERTEX_ROUTER
) {
1019 struct router_lsa_link
*l
;
1020 struct router_lsa
*rlsa
;
1023 if (IS_DEBUG_OSPF_EVENT
)
1025 "ospf_process_stubs():processing router LSA, id: %s",
1026 inet_ntoa(v
->lsa
->id
));
1027 rlsa
= (struct router_lsa
*)v
->lsa
;
1030 if (IS_DEBUG_OSPF_EVENT
)
1032 "ospf_process_stubs(): we have %d links to process",
1033 ntohs(rlsa
->links
));
1034 p
= ((uint8_t *)v
->lsa
) + OSPF_LSA_HEADER_SIZE
+ 4;
1035 lim
= ((uint8_t *)v
->lsa
) + ntohs(v
->lsa
->length
);
1038 l
= (struct router_lsa_link
*)p
;
1040 p
+= (OSPF_ROUTER_LSA_LINK_SIZE
1041 + (l
->m
[0].tos_count
* OSPF_ROUTER_LSA_TOS_SIZE
));
1043 if (l
->m
[0].type
== LSA_LINK_TYPE_STUB
)
1044 ospf_intra_add_stub(rt
, l
, v
, area
,
1045 parent_is_root
, lsa_pos
);
1050 ospf_vertex_dump("ospf_process_stubs(): after examining links: ", v
, 1,
1053 for (ALL_LIST_ELEMENTS(v
->children
, cnode
, cnnode
, child
)) {
1054 if (CHECK_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
))
1057 /* the first level of routers connected to the root
1058 * should have 'parent_is_root' set, including those
1059 * connected via a network vertex.
1063 else if (v
->type
== OSPF_VERTEX_ROUTER
)
1066 ospf_spf_process_stubs(area
, child
, rt
, parent_is_root
);
1068 SET_FLAG(child
->flags
, OSPF_VERTEX_PROCESSED
);
1072 void ospf_rtrs_free(struct route_table
*rtrs
)
1074 struct route_node
*rn
;
1075 struct list
*or_list
;
1076 struct ospf_route
* or ;
1077 struct listnode
*node
, *nnode
;
1079 if (IS_DEBUG_OSPF_EVENT
)
1080 zlog_debug("Route: Router Routing Table free");
1082 for (rn
= route_top(rtrs
); rn
; rn
= route_next(rn
))
1083 if ((or_list
= rn
->info
) != NULL
) {
1084 for (ALL_LIST_ELEMENTS(or_list
, node
, nnode
, or))
1085 ospf_route_free(or);
1087 list_delete_and_null(&or_list
);
1089 /* Unlock the node. */
1091 route_unlock_node(rn
);
1093 route_table_finish(rtrs
);
1098 ospf_rtrs_print (struct route_table
*rtrs
)
1100 struct route_node
*rn
;
1101 struct list
*or_list
;
1102 struct listnode
*ln
;
1103 struct listnode
*pnode
;
1104 struct ospf_route
*or;
1105 struct ospf_path
*path
;
1109 if (IS_DEBUG_OSPF_EVENT
)
1110 zlog_debug ("ospf_rtrs_print() start");
1112 for (rn
= route_top (rtrs
); rn
; rn
= route_next (rn
))
1113 if ((or_list
= rn
->info
) != NULL
)
1114 for (ALL_LIST_ELEMENTS_RO (or_list
, ln
, or))
1116 switch (or->path_type
)
1118 case OSPF_PATH_INTRA_AREA
:
1119 if (IS_DEBUG_OSPF_EVENT
)
1120 zlog_debug ("%s [%d] area: %s",
1121 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1122 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1125 case OSPF_PATH_INTER_AREA
:
1126 if (IS_DEBUG_OSPF_EVENT
)
1127 zlog_debug ("%s IA [%d] area: %s",
1128 inet_ntop (AF_INET
, &or->id
, buf1
, BUFSIZ
),
1129 or->cost
, inet_ntop (AF_INET
, &or->u
.std
.area_id
,
1136 for (ALL_LIST_ELEMENTS_RO (or->paths
, pnode
, path
))
1138 if (path
->nexthop
.s_addr
== 0)
1140 if (IS_DEBUG_OSPF_EVENT
)
1141 zlog_debug (" directly attached to %s\r\n",
1142 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1146 if (IS_DEBUG_OSPF_EVENT
)
1147 zlog_debug (" via %s, %s\r\n",
1148 inet_ntoa (path
->nexthop
),
1149 ifindex2ifname (path
->ifindex
), VRF_DEFAULT
);
1154 zlog_debug ("ospf_rtrs_print() end");
1158 /* Calculating the shortest-path tree for an area. */
1159 static void ospf_spf_calculate(struct ospf
*ospf
, struct ospf_area
*area
,
1160 struct route_table
*new_table
,
1161 struct route_table
*new_rtrs
)
1163 struct pqueue
*candidate
;
1166 if (IS_DEBUG_OSPF_EVENT
) {
1167 zlog_debug("ospf_spf_calculate: Start");
1168 zlog_debug("ospf_spf_calculate: running Dijkstra for area %s",
1169 inet_ntoa(area
->area_id
));
1172 /* Check router-lsa-self. If self-router-lsa is not yet allocated,
1173 return this area's calculation. */
1174 if (!area
->router_lsa_self
) {
1175 if (IS_DEBUG_OSPF_EVENT
)
1177 "ospf_spf_calculate: "
1178 "Skip area %s's calculation due to empty router_lsa_self",
1179 inet_ntoa(area
->area_id
));
1183 /* RFC2328 16.1. (1). */
1184 /* Initialize the algorithm's data structures. */
1186 /* This function scans all the LSA database and set the stat field to
1187 * LSA_SPF_NOT_EXPLORED. */
1188 ospf_lsdb_clean_stat(area
->lsdb
);
1189 /* Create a new heap for the candidates. */
1190 candidate
= pqueue_create();
1191 candidate
->cmp
= cmp
;
1192 candidate
->update
= update_stat
;
1194 /* Initialize the shortest-path tree to only the root (which is the
1195 router doing the calculation). */
1196 ospf_spf_init(area
);
1198 /* Set LSA position to LSA_SPF_IN_SPFTREE. This vertex is the root of
1201 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1203 /* Set Area A's TransitCapability to FALSE. */
1204 area
->transit
= OSPF_TRANSIT_FALSE
;
1205 area
->shortcut_capability
= 1;
1208 /* RFC2328 16.1. (2). */
1209 ospf_spf_next(v
, ospf
, area
, candidate
);
1211 /* RFC2328 16.1. (3). */
1212 /* If at this step the candidate list is empty, the shortest-
1213 path tree (of transit vertices) has been completely built and
1214 this stage of the procedure terminates. */
1215 if (candidate
->size
== 0)
1218 /* Otherwise, choose the vertex belonging to the candidate list
1219 that is closest to the root, and add it to the shortest-path
1220 tree (removing it from the candidate list in the
1222 /* Extract from the candidates the node with the lower key. */
1223 v
= (struct vertex
*)pqueue_dequeue(candidate
);
1224 /* Update stat field in vertex. */
1225 *(v
->stat
) = LSA_SPF_IN_SPFTREE
;
1227 ospf_vertex_add_parent(v
);
1229 /* RFC2328 16.1. (4). */
1230 if (v
->type
== OSPF_VERTEX_ROUTER
)
1231 ospf_intra_add_router(new_rtrs
, v
, area
);
1233 ospf_intra_add_transit(new_table
, v
, area
);
1235 /* RFC2328 16.1. (5). */
1236 /* Iterate the algorithm by returning to Step 2. */
1238 } /* end loop until no more candidate vertices */
1240 if (IS_DEBUG_OSPF_EVENT
) {
1241 ospf_spf_dump(area
->spf
, 0);
1242 ospf_route_table_dump(new_table
);
1245 /* Second stage of SPF calculation procedure's */
1246 ospf_spf_process_stubs(area
, area
->spf
, new_table
, 0);
1248 /* Free candidate queue. */
1249 pqueue_delete(candidate
);
1251 ospf_vertex_dump(__func__
, area
->spf
, 0, 1);
1252 /* Free nexthop information, canonical versions of which are attached
1253 * the first level of router vertices attached to the root vertex, see
1254 * ospf_nexthop_calculation.
1256 ospf_canonical_nexthops_free(area
->spf
);
1258 /* Increment SPF Calculation Counter. */
1259 area
->spf_calculation
++;
1261 monotime(&area
->ospf
->ts_spf
);
1262 area
->ts_spf
= area
->ospf
->ts_spf
;
1264 if (IS_DEBUG_OSPF_EVENT
)
1265 zlog_debug("ospf_spf_calculate: Stop. %zd vertices",
1266 mtype_stats_alloc(MTYPE_OSPF_VERTEX
));
1268 /* Free SPF vertices, but not the list. List has ospf_vertex_free
1271 list_delete_all_node(&vertex_list
);
1274 /* Timer for SPF calculation. */
1275 static int ospf_spf_calculate_timer(struct thread
*thread
)
1277 struct ospf
*ospf
= THREAD_ARG(thread
);
1278 struct route_table
*new_table
, *new_rtrs
;
1279 struct ospf_area
*area
;
1280 struct listnode
*node
, *nnode
;
1281 struct timeval start_time
, spf_start_time
;
1282 int areas_processed
= 0;
1283 unsigned long ia_time
, prune_time
, rt_time
;
1284 unsigned long abr_time
, total_spf_time
, spf_time
;
1285 char rbuf
[32]; /* reason_buf */
1287 if (IS_DEBUG_OSPF_EVENT
)
1288 zlog_debug("SPF: Timer (SPF calculation expire)");
1290 ospf
->t_spf_calc
= NULL
;
1292 monotime(&spf_start_time
);
1293 /* Allocate new table tree. */
1294 new_table
= route_table_init();
1295 new_rtrs
= route_table_init();
1297 ospf_vl_unapprove(ospf
);
1299 /* Calculate SPF for each area. */
1300 for (ALL_LIST_ELEMENTS(ospf
->areas
, node
, nnode
, area
)) {
1301 /* Do backbone last, so as to first discover intra-area paths
1302 * for any back-bone virtual-links
1304 if (ospf
->backbone
&& ospf
->backbone
== area
)
1307 ospf_spf_calculate(ospf
, area
, new_table
, new_rtrs
);
1311 /* SPF for backbone, if required */
1312 if (ospf
->backbone
) {
1313 ospf_spf_calculate(ospf
, ospf
->backbone
, new_table
, new_rtrs
);
1317 spf_time
= monotime_since(&spf_start_time
, NULL
);
1319 ospf_vl_shut_unapproved(ospf
);
1321 monotime(&start_time
);
1322 ospf_ia_routing(ospf
, new_table
, new_rtrs
);
1323 ia_time
= monotime_since(&start_time
, NULL
);
1325 monotime(&start_time
);
1326 ospf_prune_unreachable_networks(new_table
);
1327 ospf_prune_unreachable_routers(new_rtrs
);
1328 prune_time
= monotime_since(&start_time
, NULL
);
1330 /* AS-external-LSA calculation should not be performed here. */
1332 /* If new Router Route is installed,
1333 then schedule re-calculate External routes. */
1335 ospf_ase_calculate_schedule(ospf
);
1337 ospf_ase_calculate_timer_add(ospf
);
1339 if (IS_DEBUG_OSPF_EVENT
)
1341 "%s: ospf install new route, vrf %s id %u new_table count %lu",
1342 __PRETTY_FUNCTION__
, ospf_vrf_id_to_name(ospf
->vrf_id
),
1343 ospf
->vrf_id
, new_table
->count
);
1344 /* Update routing table. */
1345 monotime(&start_time
);
1346 ospf_route_install(ospf
, new_table
);
1347 rt_time
= monotime_since(&start_time
, NULL
);
1349 /* Update ABR/ASBR routing table */
1350 if (ospf
->old_rtrs
) {
1351 /* old_rtrs's node holds linked list of ospf_route. --kunihiro.
1353 /* ospf_route_delete (ospf->old_rtrs); */
1354 ospf_rtrs_free(ospf
->old_rtrs
);
1357 ospf
->old_rtrs
= ospf
->new_rtrs
;
1358 ospf
->new_rtrs
= new_rtrs
;
1360 monotime(&start_time
);
1361 if (IS_OSPF_ABR(ospf
))
1362 ospf_abr_task(ospf
);
1363 abr_time
= monotime_since(&start_time
, NULL
);
1365 /* Schedule Segment Routing update */
1366 ospf_sr_update_timer_add(ospf
);
1369 monotime_since(&spf_start_time
, &ospf
->ts_spf_duration
);
1372 if (spf_reason_flags
) {
1373 if (spf_reason_flags
& SPF_FLAG_ROUTER_LSA_INSTALL
)
1374 strncat(rbuf
, "R, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1375 if (spf_reason_flags
& SPF_FLAG_NETWORK_LSA_INSTALL
)
1376 strncat(rbuf
, "N, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1377 if (spf_reason_flags
& SPF_FLAG_SUMMARY_LSA_INSTALL
)
1378 strncat(rbuf
, "S, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1379 if (spf_reason_flags
& SPF_FLAG_ASBR_SUMMARY_LSA_INSTALL
)
1380 strncat(rbuf
, "AS, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1381 if (spf_reason_flags
& SPF_FLAG_ABR_STATUS_CHANGE
)
1382 strncat(rbuf
, "ABR, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1383 if (spf_reason_flags
& SPF_FLAG_ASBR_STATUS_CHANGE
)
1384 strncat(rbuf
, "ASBR, ",
1385 sizeof(rbuf
) - strlen(rbuf
) - 1);
1386 if (spf_reason_flags
& SPF_FLAG_MAXAGE
)
1387 strncat(rbuf
, "M, ", sizeof(rbuf
) - strlen(rbuf
) - 1);
1389 size_t rbuflen
= strlen(rbuf
);
1391 rbuf
[rbuflen
- 2] = '\0'; /* skip the last ", " */
1396 if (IS_DEBUG_OSPF_EVENT
) {
1397 zlog_info("SPF Processing Time(usecs): %ld", total_spf_time
);
1398 zlog_info("\t SPF Time: %ld", spf_time
);
1399 zlog_info("\t InterArea: %ld", ia_time
);
1400 zlog_info("\t Prune: %ld", prune_time
);
1401 zlog_info("\tRouteInstall: %ld", rt_time
);
1402 if (IS_OSPF_ABR(ospf
))
1403 zlog_info("\t ABR: %ld (%d areas)", abr_time
,
1405 zlog_info("Reason(s) for SPF: %s", rbuf
);
1408 ospf_clear_spf_reason_flags();
1413 /* Add schedule for SPF calculation. To avoid frequenst SPF calc, we
1414 set timer for SPF calc. */
1415 void ospf_spf_calculate_schedule(struct ospf
*ospf
, ospf_spf_reason_t reason
)
1417 unsigned long delay
, elapsed
, ht
;
1419 if (IS_DEBUG_OSPF_EVENT
)
1420 zlog_debug("SPF: calculation timer scheduled");
1422 /* OSPF instance does not exist. */
1426 ospf_spf_set_reason(reason
);
1428 /* SPF calculation timer is already scheduled. */
1429 if (ospf
->t_spf_calc
) {
1430 if (IS_DEBUG_OSPF_EVENT
)
1432 "SPF: calculation timer is already scheduled: %p",
1433 (void *)ospf
->t_spf_calc
);
1437 elapsed
= monotime_since(&ospf
->ts_spf
, NULL
) / 1000;
1439 ht
= ospf
->spf_holdtime
* ospf
->spf_hold_multiplier
;
1441 if (ht
> ospf
->spf_max_holdtime
)
1442 ht
= ospf
->spf_max_holdtime
;
1444 /* Get SPF calculation delay time. */
1446 /* Got an event within the hold time of last SPF. We need to
1447 * increase the hold_multiplier, if it's not already at/past
1448 * maximum value, and wasn't already increased..
1450 if (ht
< ospf
->spf_max_holdtime
)
1451 ospf
->spf_hold_multiplier
++;
1453 /* always honour the SPF initial delay */
1454 if ((ht
- elapsed
) < ospf
->spf_delay
)
1455 delay
= ospf
->spf_delay
;
1457 delay
= ht
- elapsed
;
1459 /* Event is past required hold-time of last SPF */
1460 delay
= ospf
->spf_delay
;
1461 ospf
->spf_hold_multiplier
= 1;
1464 if (IS_DEBUG_OSPF_EVENT
)
1465 zlog_debug("SPF: calculation timer delay = %ld msec", delay
);
1467 ospf
->t_spf_calc
= NULL
;
1468 thread_add_timer_msec(master
, ospf_spf_calculate_timer
, ospf
, delay
,